www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 아이디어: #큐 큐를 이용해서 n까지의 수를 모두 넣은 후 앞에서부터 차례대로 제거하면서 제거한 수를 다시 큐에 집어넣는 형태로 반복한다. 파이썬에서 queue를 구현하는 방법 1. 리스트 - 비효율적임 2. Queue # 내장 함수 queue를 사용하여 구현 import queue q = queue.Queue() q.put("a") q.put("b") q.put("c") q.qsize() # 3 q.get() # 'a' q.qsize() # 2 근데 queue를 이용해서 문제를 풀었더니 시간초과가 나..
복습
www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 아이디어: 이분탐색 이분탐색을 이용하여 푸면 된다. 하지만, 구현 과정에서 그냥 mid 값을 출력하니 틀렸다. 조금만 생각해보면 당연한 것이다. 조건에 맞을 경우에만 답을 업데이트해주고 그 답을 출력해야 한다. 그런데 또 파이썬으로 제출하면 시간초과가 떠서 pypy로 제출했는데, 질문을 보니 시간을 단축할 수 있는 방법을 생각해보라고 해서 이왕 정렬하는 거 배열의 끝에서 ..
www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 아이디어: #정렬 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다. 따라서 정렬 조건은 1. 최종점수 2. 풀이를 제출한 횟수 3. 마지막 제출 시간 이다. 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 한 문제에 대한 풀이를 여러번 제출할 수 있으며 그 중 최고 점수가 그 문제의 최종 점수이다. 입력..
www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 아이디어: 뭔가 일단 정렬을 해야 할 것 같다. 근데 이걸 투 포인터로 어떻게 풀 수 있을까? 모든 경우를 찾아본다면, 가능한 두 수를 모두 뽑고 그 합과 같은 숫자가 있는지 탐색할 수 있을 것이다. 탐색은 이분 탐색이 가능할 것 같다. 근데 이게 시간 안에 풀어질까..? 그래서 구글링함^^ 내 생각이 조금은 맞았다. 대신 반대로, arr에 있는 모든 수를 돌면서 합이 arr[i]가 되는 두 수가 있는지를 찾는다. 이때 투 포인터를 이용한..
www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 아이디어: 투 포인트로 구현하면 되고, 대충 로직은 강의 들으면서 이해했는데 구현 과정에서 애를 먹었다. 이래서 어설프게 알면 안돼..ㅠㅠ left, right 포인터를 0, 0 으로 초기화하고 합result와 출력할 답 ans 도 0으로 초기화한다. 무한루프를 돌면서 합이 m보다 클 경우에는 합을 줄여야 하므로 result에서 arr[left]값을 빼고 left++한다..
www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 아이디어: 이분 탐색으로 푼다는 게 무조건 mid 값을 찾는다는 게 아닌가보다..((아닐수도)) 1. 정렬 2. high = n-1, low = 0으로 포인터를 설정하고, while문을 수행하면서 특성값을 구하고 절댓값을 취하여 최솟값을 업데이트한다. 특성값이 음수면 low++(0에 가까워지려면 커져야 되니까), 양수면 high--(0에 가까워지려면 작아져야 되니까) impor..
www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 아이디어: 시간을 이분탐색하여 시간의 최솟값을 찾는다. import sys n, m = map(int, sys.stdin.readline().split()) time = [] for _ in range(n): time.append(int(sys.stdin.readline())) high = 10**18 low = 1 ans = high while (high>=low): mid = (high+low..
www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 아이디어: 배낭 문제 dp[i][k] = 최대 배낭 수용 무게가 k일때, i번째 까지의 물건을 봤을 때 가치의 최대합 i번째 물건을 넣을 수 있는 경우(k>=wi): max(dp[i-1][k-wi]+vi, dp[i-1][k]) i번째 물건을 넣을 때 vs 넣지 않을 때 가치가 더 큰 것 선택 i번째 물건을 넣을 수 없는 경우(k dp[n][k] ..
www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 문제 제목이 이게 무슨 개소리야;; 왠지 좆같은데.. 한남 냄새가 나.. 아이디어: 1과 5로만 구성된 N자리 양의 정수 중, 15의 배수가 몇 개인지 15의 배수: 일의 자리는 0 or 5여야 하므로 일의 자리는 무조건 5, 각 자리의 합이 3의 배수여야 함. 5가 사용된 갯수 i에 따라 (1~N) 각 자릿수의 합을 구할 수 있음. -> 3의 배수인지 확인, 조합 이용(n-1Ci-1) import sys n = int(sys.stdin.readline()) ans = 0 #조합 구하기 N=n-1 dp =..
www.acmicpc.net/problem/1757 1757번: 달려달려 어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정 www.acmicpc.net 아이디어: DP를 구성하는 방법을 떠올리는 방식이 어렵다. 조건 - 1분을 달리면 지침 지수는 1이 올라간다. 1분을 쉬면 지침 지수는 1 내려간다. -> 지침지수가 0일 때 쉬어도 그대로 0이다. - 쉬기 시작하면 지침지수가 0이 되기 전에는 다시 달릴 수 없다. - 달리기가 끝나면 지침지수는 0이 되어야 한다. -> 마지막 n분째에는 달릴 수 없다. DP[x][y][z] = x초에 y의 지침지수를 가지고 z는 뛰고 있..
