파게로그

문제 링크: N번 제목 https://www.acmicpc.net/problem/9184 어떤 점에서 동적 계획법 문제라고 생각할 수 있을까요? 복잡하게 생각할 것 없이, a > 20 or b > 20 or c > 20인 케이스만 해도 w(20, 20, 20)를 호출하며, 이는 4번 케이스에 해당하는데 각각 w를 4번 호출하므로 값을 기억하는 편이 편합니다. 한편, a, b, c가 증가할 수록 w() 호출값이 커지는 형태인데 w(50, 50, 50)의 반환값이 예제에서 정의되어 있으므로 int 범위를 넘을 걱정은 하지 않아도 됩니다. #include int a, b, c, d[51][51][51]; int w(int a, int b, int c) { if (a 20) return d[a][b][c] = ..

문제 링크: 1744번 제목 https://www.acmicpc.net/problem/1744 다행히 생각보다는 분기를 많이하지 않았지만 그렇다고 해서 복잡하지 않은 문제는 아닙니다. 저는 수열을 정렬한 후, 먼저 양수 부분수열을 처리하고, 0 또는 음수인 부분수열을 처리하는 방식으로 진행했습니다. 코드에서와 마찬가지로, 여기서도 편의상 내림차순으로 정렬하겠습니다. 7 4 3 3 2 1 0 -2 -2 -3 -4 -5 -5 -6 위에서 양수 부분수열은 하늘색 부분입니다. 그리디하게 큰 수끼리 곱해서, 즉 앞에서부터 두 개씩 곱해서 더해줍니다. 그 후, 주황색 부분수열도 절댓값이 큰 수부터, 즉 뒤에서부터 두 개씩 곱해서 더해줍니다. 여기서 0은 음수와 구분할 필요가 없는데, 0이라고 하더라도 어차피 음수와..

문제 링크: 1807번 제목 https://www.acmicpc.net/problem/1807 가장 먼저, K의 범위를 통해서 수를 직접 써가는 나이브한 풀이는 불가능하다는 것을 알 수 있습니다. 대신 우리가 어떤 힌트를 얻을 수 있냐고 한다면, K번째 수를 바로 구하는 것은 어려운데, (가) 어떤 수 N으로 시작하는 수가 문자열에서 몇 번째에 오는지는 구해볼 만하다는 것입니다. 예를 들기 위해서 S를 직접 써보면 다음과 같습니다. 12203245260728921001121213214015216172180... K=40일 때 답은 8이고, 그 수는 180으로서 N=18로 시작하는 수입니다. 이를 통해 N은 K보다 작거나 같다는 사실을 알 수 있습니다. 다시 말해, (나) S[K]를 구하고자 할 때, S[..

문제 링크: 1022번 소용돌이 예쁘게 출력하기 https://www.acmicpc.net/problem/1022 r1, c1, r2, c2의 범위를 고려하면 일단 10001 * 10001개, 즉 대략 1억 개를 배열에 채워넣는 것으로서 시간복잡도에서는 문제가 없습니다. 다만 제출해보니 메모리 초과가 뜨는데요, 여기서 불필요한 메모리는 실제로 출력되지 않아도 될 부분입니다. 일단 배열을 채울 텐데요, 가상 배열의 (5000, 5000)이 문제 배열의 (0, 0)에 해당합니다. 즉 코드에서 r, c는 가상 배열 좌표인데요, 이를 문제 배열 좌표로 바꿀 때에는 5000을 빼면 됩니다. (5000, 5000)에서 출발해서 소용돌이 모양으로 가상 배열을 순회하되, 문제 배열 좌표가 (r1, c1)과 (r2, c..

문제 링크: 1300번 K번째 수 https://www.acmicpc.net/problem/1300 이 문제를 읽은 뒤 parametric search라는 알고리즘 자체를 떠올리는 것 자체가 난해한 과정이며, 해당 알고리즘으로 풀 수 있는 문제라는 것을 인지하더라도 다소 헤매게 되어있습니다. 일단 naive한 풀이는 왜 안될까요? N은 105보다 작거나 같은 자연수이므로 배열의 모든 숫자를 일일이 나열하여 정렬하고자 하면 1010개에 달하는 수를 다루어야 하기 때문입니다. 일일이 각 숫자의 개수를 모두 계산하자니 규칙을 찾기가 힘들 뿐더러, 결국 많은 양의 연산이 필요합니다. 우리는 이 문제를 "어떤 수 x가 i번째 숫자일 때, i는 k보다 크거나 같은가?"라는 결정 문제로 바꾸어 풀 수 있습니다. 간단..

문제 링크: 13422번 제목 https://www.acmicpc.net/problem/13422 문제를 읽기만 해도 풀이가 보일 듯한 쉬운 문제로 보입니다. 네, 실제로 쉬운 문제가 맞습니다. 하지만, (슬라이딩 윈도우로 푼다는 가정 아래에) 숨겨진 함정이 하나 있습니다. 바로 n과 m이 같을 때입니다. 일단 n = 4, m = 3이면 어떨까요? 처음 2가지 경우만 보더라도, 윈도우를 이동시켰을 때 서로 다른 부분집합이 선택된다는 것을 알 수 있습니다. {1, 2, 3}, {2, 3, 4}, {3, 4, 1}, {4, 1, 2} 이렇게요. 하지만 n = m = 4인 경우는 어떨까요? 마찬가지로 처음 2가지 경우만 보겠습니다. 이 때에는 윈도우를 이동시켜도 동일한 부분집합이 선택된다는 것을 알 수 있습니..

문제 링크: 10836번 제목 https://www.acmicpc.net/problem/10836 입력받은 배열을 일반적인 변수로 두고, 각 칸이 어떤 값을 가지는지 살펴볼 수 있다. 예를 들어, 벌집의 크기가 5라면 다음과 같다. 그리고 입력 조건의 "본문에서 보인 것과 같이, 자라는 크기를 제일 왼쪽 아래 칸에서 시작해서 위쪽으로 올라가서 제일 위쪽에 도착하면 오른쪽으로 이동하며 읽었다고 하자. 이 값들은 감소하지 않는다."에 따라서, a < b < c < ... < i를 만족하므로 위 표는 아래와 같다. 이 때 a, b, c, ..., i는 0, ..., 0, 1, ..., 1, 2, ..., 2와 같은 형태일 것이므로 a, b, c, ..., i 각각에 대해 누적 합이 얼마였는지만 알고 있으면 각..

문제 링크: 1146번 지그재그 서기 https://www.acmicpc.net/problem/1146 가장 나이브하게 풀면 어떻게 될까? 어떤 숫자가 몇 번째 줄에 위치한다는 것을 정한 상태에서, 다른 숫자의 사용 여부를 저장해둔 다음 안 쓴 숫자 중 하나를 골라서 다음 줄의 상태를 탐색해나갈 수 있다. 여기서 조금 더 개선해보면, 자신보다 작은 숫자와 큰 숫자를 각각 별도로 가지고 있으면 편할 것이다. 여기서 조금 더 생각해보면, 숫자 자체는 의미가 없고 숫자끼리의 대소 관계에만 의미가 있음에 착안하여 알고리즘을 개선할 수 있다. 위와 같은 사고 과정을 거치는 것이 이상적이긴 하며, 실제로는, (다행히?) DP로 풀어야겠다는 생각이 먼저 들기는 했다. N