[python]백준 4811번 : 알약

https://www.acmicpc.net/problem/4811

문제

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

입력

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

나의 답

순열

W(알약 하나)가 하나 나오면 무조건 H(알약 반 개)가 뒤에 하나 나와야 함

처음에는 W로 시작

길이는 고정으로 2N

W가 N개, H가 N개인데 W의 갯수보다 H의 갯수가 많아지는 부분이 존재해서는 안됨

=> 순열로 하는 것은 너무 복잡함

 

알고리즘 구성

2020-04-19에 수정되었음

<1안>

func(2N-1,W,H)
    if(2N-1이 1이면) // 마지막은 어차피 H
        count++;
        return
    if(W가 N-1이면) // 나머지는 어차피 H이므로
        count++;
        return
    if(W>H)
        func(2N-2,W+1,H)
        func(2N-2,W,H+1)
    else
        func(2n-2,W+1,H)

 한 알을 먹으면 W를 늘리고 반 알을 먹으면 H를 늘린다. W보다 H가 커지는 경우는 없어야 하므로 둘이 같을 경우 W를 늘리게 재귀를 호출하고, W가 큰 경우 W를 늘리는 경우와 H를 늘리는 경우 각각을 호출한다.

 이렇게 알고리즘을 구성하면 2N-2번 재귀를 타므로 2^59 = 약 10^18의 재귀함수가 호출된다. 당연히 시간초과이다.

어떻게 DP를 구현할까 생각해보다가 얼마 전 풀었던 문제의 방법이 떠올라 구현해보았다.

 

<2안>

 이렇게 H와 W를 배열로 나타내면 a처럼 처음에는 W가 1이고 H가 0일 때부터 시작한다(첫 날에는 무조건 한 알을 꺼내야 하므로 W가 1부터 시작). b를 보면 W가 H보다 많으면 한 알을 꺼내거나 반 알을 꺼낼 수 있으므로 배열에서 오른쪽과 아래로 나아갈 수 있다. c에서 보여지듯이 W가 H와 같으면 무조건 한 알을 꺼내야 하므로 오른쪽으로만 나아갈 수 있다.

 이런 식으로 H 행 갯수만큼 for문을 돌리고 그 안에서 W 열 갯수만큼 for문을 돌리면서 각각의 방향에 현재의 값을 더해주면 다음과 같은 그림이 완성된다.

 

 따라서 N이 4일때의 답은 14이다. testcase가 여러 개이므로 한 번 계산해두면 계속 이 배열을 이용하여 답을 낼 수 있다. N이 3일 때는 위의 그림에서 (3,3) 위치에 해당하는 5가 답이다.

 이렇게 배열로 표현한것은 사실 파란색으로 표시된 곳을 map이라고 봤을 때, (0,1)에서 (N,N)까지 가는 경로의 갯수이다.

시간 복잡도는 이중 for문의 갯수만큼 이므로 N^2이다.

최대 9*10^2

 

다른 답

• 일정 규칙이 있으므로 방정식을 이용한 풀이도 잘 생각하면 나올 수 있다.

input_list = list()

while(1):
    n = int(input())
    if n:
        input_list.append(n)
    else:
        for tmp in input_list:
            r=1
            for n in range(2*tmp,tmp,-1):
                r*=n
            for n in range(1,tmp+2):
                r //=n
            print(r)
        break

• W와 H를 현재 남아있는 알약으로 생각하고 완전탐색 + DP

  W가 있으면 W를 1줄이고 H를 1늘리는 재귀 호출

  H가 있으면 H를 1줄이는 재귀 호출

  이래도 재귀가 최대 10^9라서 시간초과가 나올 것 같은데 안나오나보다 ㅇㅅㅇ

  http://blog.naver.com/PostView.nhn?blogId=jhc9639&logNo=221801894374