BOJ 2225 합분해

예전에 여러 번 풀었고, 간단한 dp문제 같아 보이지만 중요한 문제이다.
지금부터 다시 복습해 보겠다.

0부터 N까지의 정수 중 k개를 더 해서 그 합이 N이 되는 경우의 수를 구해야 한다.
그리고 덧셈의 순서가 바뀌면 다른 경우로 센다(1+2와 2+1은 다르다.) 또한 한 개의 수를 여러번 써도 된다.

d[N][k] = k개를 더해서 그 합이 N이 되는 경우의 수
로 놓으면, d[N][k] = SUM(x=0~N)d[N-x][k-1]; 로 하면 될 것 같다. N이 200, k가 200이므로 O(N세제곱)만에 될 것 같다. 구현해 봐야겠다. 구현에 좀 실수가 있어서 WA를 두 번 받고 결국 AC를 받았다. 재귀로 구현했는데, 24ms의 시간이 나온다. 이것을 for문 dp로 구현하면 조금 더 시간이 줄어들 것이다. 한 번 구현해 보겠다. WA를 한 번 받고, AC를 받았다. 시간은 16ms로 줄었다. 자 이제 이것을 0ms로 줄여볼 차례이다.

먼저 d[n][k]는 항상 d[n-x][k-1]값들의 합으로만 이루어져 있으므로 즉, k-1번째 값들만 이용하기 때문에 sliding window기법을 써서 메모리를 확 줄일 수 있다.
하지만 많은 WA를 받았는데, 여기서 주의해야 할 것은 d[n][k%2]는 d[n-x][k-1]값들의 합인데, sliding window기법을 쓸 때는 0으로 초기화가 되있지 않을 수 있기 때문에 항상
d[n][k%2]값을 0으로 초기화해줘야 한다. 그렇지 않으면 전에 있던 값에 누적해서 덧셈이 되어 엉뚱한 값이 나오게 된다. 결국 AC를 받았는데, 이 역시 16ms...메모리는 줄었지만, 시간은 줄지 않았다. 왜냐하면 여전히 O(N세제곱)이기 때문이다. 시간을 줄이기 위해서는 다른 방법이 필요하다.

for문 dp로 할 때 쓸 수 있는 방법인데, for문을 보면 3중 for문이다.
d[n][k]가 있으면, for문 2개는 n과 k를 담당하고, 가장 안쪽 for문에서 x를 담당하는데,
d[n][k]=SUM(x=0~n) d[n-x][k-1] 이므로 가장 안쪽 for문이 x=0~n까지 돌게 된다.
그런데, 잘 보면 d[n][k]에 더해지는 수들은 d[0][k-1]~d[n][k-1] 이다. 이 값들은 (제일 바깥쪽 for문이 k를 담당하는 for문 이라면) 직전에 구한 값들이다. 그렇기 때문에 d[n][k]를 구하기 직전에 d[n][k-1]값들을 구하면서 이 값들의 부분합(누적합)을 미리 저장해 놓으면 3중 for문에서 x를 담당하는 가장 안쪽 for문은 돌 필요가 없다.
이렇게 하면 결국 O(N제곱)만에 가능하다. 게다가 sliding window까지 쓰면 메모리도 줄일 수 있다. AC를 받았다.

BOJ 1222 홍준 프로그래밍 대회

대회 참여 의사가 있는 학교의 수와 각 학교의 학생 수가 주어지는데, 대회 주최측에서 팀원 수를 정해주면 반드시 그 팀원 수대로 팀을 만들어야 하고 한 학교의 학생이 전원 참여할 수 있을 때만 그 학교가 참가할 수 있다. 즉 학생 수가 주최측에서 정한 팀원 수로 나누어 떨어져야 한다. 그리고 그렇게 참가한 학교의 팀 중 1위 팀만 본선에 진출할 수 있다. 즉 본선은 참가한 학교당 팀원 수(한 팀)만큼만 진출할 수 있다. 그리고 본선에는 적어도 2팀은 진출하게 해야한다는 조건이 있으므로 적어도 2개의 학교의 학생수가 팀원의 수로 나누어 떨어져야 한다.
이 때, 팀원 수를 잘 설정해서 본선에 참가할 수 있는 사람의 수의 최대값을 구하는 문제이다.

결국 본선에 진출할 수 있는 사람의 수는
(1.학생 수가 팀원 수로 나누어 떨어지는 학교의 수)*(2.팀원 수) 가 될 것인데, 1.학교의 수는 2개 이상이 되야 한다. 그럼 1부터 2000000까지의 팀원수를 다 넣어보면서 위의 조건을 만족하는 경우의 값을 구해서 그 중 최대를 구하면 될 것이다. 하지만 학교의 수는 200000...
시간이 너무 오래걸린다.

BOJ 2404 단위 분수로 분할

분자가 1이고 분모가 양수인 분수를 단위 분수라고 하고 p/q를 단위분수의 합으로 나타내었을 때 p/q를 단위분수로 분할했다고 말한다.
입력으로 p, q, a, n이 주어지면 분수 p/q를 n개 이하의 단위 분수의 합으로 나타내는 경우의 수를 구하는 것이 문제인데, 이 때 분할을 이루는 분모의 곱이 a이하여야 한다.

dp 느낌이 든다.
d[p][q][a][n]= p/q를 n개 이하의 (분할을 이루는 분모의 곱이 a이하이면서 ) n개 이하의 단위 분수의 합으로 나타내는 경우의 수
로 하면 d[p][q][a][n]=SUM( d[np][nq][a/aq][n-1] )... 대충 이런 식으로.. 하지만, 배열을 d[p][q][a][n]으로 설정할 경우 메모리 초과가 분명하다.

a가 무려 최대 12000인데 a를 뺄 수 있을까? a를 그냥 parameter로 넘겨주면 어떨까? 음 안될 것 같다. p, q, n이 같아도 a가 다르면 달라질 수 밖에 없다... 그렇다면 a를 parameter로 보내되, a보다 더 작은 값으로 a를 대체할 수는 없을까? 음... 아니면 p나, q중 하나만 줄여도 메모리 초과는 안 날텐데, p나 q중 하나를 없앨 수 있을까?

방금 맞은 사람 목록을 봤는데, 메모리뿐만 아니라 코드 길이도 매우 짧은 편이다. 비록 맞은 사람이 2명밖에 없긴하지만... 음... dp가 아닌가? 다르게 생각해 봐야겠다.

n이 최대 7이니까 일일이 다 해보는 방식은 어떨까?
좀 더 고민을 해 봤는데, 분할을 이루는 분모의 곱이 a이하여야 하므로 이 말은 즉, 분할을 이루는 분모의 곱이 a이하의 어떤 수가 된다는 것으로도 볼 수 있다. 예를 들어 a가 12000이고, n이 7이면 1부터 12000까지 모든 수를 각각 분할을 이루는 분모의 곱으로 보면서 각 경우에 대해서 n은 1부터 7까지 보면서 단위 분수의 조합을 구해서 합해보고
비교할 땐 그 합한 값이 p/q와 p%q와 같은지 살펴보고 같으면 count해주는 식으로... 좀 복잡할 것 같지만 한 번 구현해 봐야겠다. 아... 이렇게 하면 단위 분수의 조합을 구하는데 시간이 너무 많이 걸린다.

음 일단 넘어가고.. 백준님의 해설 강의를 들어야겠다.

백트래킹... 재귀를 쓰려면 문제가 재귀적인 형태를 띄는지 봐야한다.
non decreasing 으로 뽑으면 중복되지 않게 뽑음.(조합)

BOJ 2295 세수의 합

자연수들로 이루어진 집합에서 적당히 세 수를 골라서(같은 수를 골라도 된다) 세 수의 합 d를 구했을 때 d가 그 집합의 원소가 되는 d 중에서 최대값을 구하는 문제이다.

일단, N제한이 1000이라 3가지 수를 고르는(같은 수도 포함) 방법의 수는 1000의 세제곱이 되어 다 해보는 것은 시간초과가 날 것이다.

문득 dp로 해보면 어떨까하는 생각이 들었다. d[val][n] = n개의 수를 더해서 val이 될 수 있는지 없는지. d[val][n]=d[val-a][n-1].. 이런 식으로... 근데 val이 최대 2억이라 메모리 초과이다.

BOJ 2411 아이템 먹기

N*M모양 맵에 아이템과 장애물이 있고, 맨 왼쪽 아래에서 출발해서 아이템을 모두 먹고 맨 오른쪽 위에 도착하는 경로의 수를 구하는 문제이다.
장애물은 지나갈 수 없고, 이동할 때는 오른쪽이나 위쪽으로 밖에 이동하지 못한다.

d[r][c][k] = (1, 1)에서 시작해서 (r, c)까지 아이템 k개를 먹으며 가는 경로의 수
로 놓으면 될 것 같은데... 아이템이 최대 10000개까지 있을 수 있는데... 오른쪽이나 위쪽으로 밖에 이동하지 못하니까 아이템은 최대 N+M-1개까지만 먹을 수 있다.
그렇기 때문에 d[r][c][k]의 배열 크기는 d[100][100][10000]이 아니라 d[100][100][200]으로 하면 될 것이다.

또 하나 생각나는 점이 주어지는 아이템이 정상적으로 이동하면서 다 먹을 수 있게 주어졌다면 아이템 방문 순서는 정해져 있다는 것이다. 오른쪽이나 위쪽으로만 이동하니까 아이템은 행, 열이 둘다 작거나 같은 것부터 이동해야 한다. 예를 들어 아이템이 (r1, c1), (r2, c2)가 있고, r1<=r2, c1<=c2이면 (r1, c1)부터 방문해야 한다. 아직 이것을 어떻게 적용시켜야 할지는 모르겠어서 일단 위에서 생각한대로 풀어 봐야겠다.

AC를 받았다. 근데 메모리와 실행 시간이 꽤 큰 편이다.

그래서 다른 분들 코드를 좀 봤더니 다들 d[r][c]로만 하신 것 같다. 내가 아까 처음에 생각했던 아이템의 방문 순서나 경로는 행, 열이 둘다 작거나 같은 것부터 먹으면서 가는 것이 맞다. 그래서 좀 더 생각을 해서 다시 코드를 짰다.
d[r][c] = (r, c)에서 시작해서 (n, m)까지 아이템을 모두 먹으며 가는 경로의 수
로 놓고, item의 좌표를 sorting해서 작은 것을 기준으로 길을 탐색한다. 위나, 오른쪽으로만 가야하므로 첫번째 아이템을 방문하기 전에 첫번째의 좌표보다 더 큰 좌표로 이동하면 안된다! 그래서 첫번째 아이템보다 더 행과 열이 작은 좌표로만 이동하는 경우만 허용하고, 만약 첫번째 아이템의 좌표에 도착하면 parameter로 보낸 아이템의 index를 index++해서 다음 아이템을 기준으로 또 길을 찾는다 . 그리고 마지막 n, m까지 도달하게 하기위해 item을 sorting한 후 item[a].r과 item[a].c에 n과 m을 넣어놨다.

이렇게 하면 자연스레 모든 아이템을 먹으면서 이동하게 되고 모든 아이템을 먹을 수 있는 경로만 이동하게 된다. 즉 무의미한 경로로 전혀 가지 않게되어 시간도 더 줄어드는 것 같다.
그래서 결국 AC를 받았다. 처음엔 그냥 다음에 할까 생각하면서 미루려고(피하려고) 했는데, 막상 해보니 할 만하고 메모리와 시간을 둘 다 줄여서 기분이 좋다.

BOJ 1322 X와 K

자연수 X와 K가 주어지면
X + Y = X | Y 를 만족하는 K번째로 작은 Y를 구해야 하는데,
일단 X+Y는 일반적인 덧셈이고, X|Y는 비트 or 연산이기 때문에 X+Y = X|Y가 되려면
X와 Y를 비트로 나타냈을 때, 겹치는 1이 없으면
X+Y = X|Y가 될 것이다. 겹치는 1이 있을 경우 X|Y를 하면 그냥 똑같이 1이 되지만, X+Y를 하면 덧셈이 되기 때문이다.
그렇다면 X와 K가 주어지면, 일단 X를 비트로 바꾼 후, 비트가 1인 부분은 0으로 채우고, 비트가 0인 부분을 (K-1)값의 비트로 채워주면 될 것이다.... 가 아니라 K값의 비트로 채워줘야 한다. 이 문제에 Y값의 조건은 나와있지 않지만 예제를 보면 Y값은 자연수인 것으로 보인다.
자연수라면 0은 안되기 때문에 K값의 비트로 채워줘야 K번째로 작은 수가 될 것이다.

그리고 내가 처음 고민했던 것이 만약 Y의 조건이 정수라면? 그럴 경우에는 이렇게 간단하게 못 풀 것 같다. Y가 음수인 경우가 좀 처리하기 힘들어 보인다.
예를 들어 4 + -6 == 4 | -6 이다.

일단 Y는 자연수라고 알고 풀어야겠다.
비트연산에 익숙하지 않아서 그런지 구현하는 게 좀 까다로웠다.
WA를 받았다... 예제도 넣어보고 살펴보다 보니... long long형을 썼는데, 1<<i 할 때 1dp LL을 안 붙여주는 실수를 했다. 고쳐서 AC를 받았다.

BOJ 2376 단말 정점들의 거리

이 문제는 잘 이해가 안된다.
단말 정점은 자식 정점이 없는 정점을 말하고 문제에서 주어지는 트리는 자식이 없거나 자식이 있다면 두 개의 자식 정점을 가져야하는 이진 트리라고 한다.

그러면 한 가지 형태의 트리밖에 안 나올 것 같은데.. 그리고 또 단말 정점 사이의 거리는 뭔지도 잘 모르겠다... 아.. 백준님의 강의 자료에서 예제 설명을 해놓은 것을 보고 알았다.
한 가지 형태의 트리밖에 나오는 것이 아니다! 그리고, 단말 정점 사이의 거리는 단말 정점 사이의 간선의 개수로 보면된다. 결국 입력으로 주어진 단말 정점 사이의 거리를 이용해서 트리를 만드는 문제이다.

inorder로 탐색을 할 때 단말 정점이 나오는 순서대로 1, 2,...n번으로 번호를 붙여줬다는 것과 어떤 정점에 자식이 있다면 반드시 두 개의 자식(정점)을 갖는다는 점을 활용해보면 트리를 그릴 수 있을 것 같다.

입력으로 1, 2번 사이의 거리, 2, 3번 사이의 거리, ... n-1, n번 사이의 거리가 주어지는데, 입력 순서대로 트리를 그려보면 될 것이다.

예제로 해보면, 1, 2번 사이의 거리가 4인데, 1번이 제일 왼쪽, 2번이 왼쪽에서 두 번째 단말 정점이 되므로 1번의 부모 정점의 바로 오른쪽 자식 정점으로 2번이 붙어야 하는데, 거리가 4이므로 오른쪽 자식 정점의 왼쪽 자식으로 두 번 내려가면 거리가 4가 차이가 난다. 그리고 그렇게 되면 3번은 자연스레 2번의 부모의 오른쪽 자식에 붙게 되는데 그럼 거리차이가 2가 나는 것도 성립한다. 이제 남은 것은 4번인데 4번은 마지막 남은 단말정점 자리(제일 오른쪽)가 될 것이고 그러면 3번과의 거리도 입력처럼 3이 된다. 이제 우리가 구하고자 하는 것은 1, 3번 사이의 거리인데 완성된 트리에서 보면 4만큼 차이가 난다.

이제 이해는 됐는데, 문제는 이것을 어떻게 구현하냐이다.

출처 : 백준님 강의, 강의 자료