[Python] BOJ_4811_알약

dkgusdkfk·2023년 4월 10일
0

STUDY

목록 보기
16/43

문제

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

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

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

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

입력

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

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

출력

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


code1

N = int(input())

while N != 0:
    dp = [[0] * (N+1) for _ in range(N+1)]

    for i in range(N+1):	# w가 없고 h만 남아있다면 방법은 1개뿐 -> 미리 1로 채우기
        dp[0][i] = 1
        
    for i in range(1, N+1):
        for j in range(i, N+1):	# H의 개수가 W의 개수보다 많으면 안되므로 i부터
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    print(dp[N][N])
    N = int(input())

입력마다 dp 생성 시 중복 생성 발생
시간을 줄이기 위해 아래 코드(code2)로 수정
미리 dp 생성 후 입력 시 프린트만!

code2

dp = [[0] * 31 for _ in range(31)]

for i in range(31):		# w가 없고 h만 남아있다면 방법은 1개뿐 -> 미리 1로 채우기
    dp[0][i] = 1
for i in range(1, 31):
    for j in range(i, 31):	# H의 개수가 W의 개수보다 많으면 안되므로 i부터
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

while True:
    N = int(input())
    if N == 0:
        break
    print(dp[N][N])

1개의 댓글

comment-user-thumbnail
2023년 4월 14일

물론 알고 있겠지만, sys.stdin.readline 쓰는 게 나을듯?
근데 gpt가 "입력 갯수가 1000개 정도라면 input()과 sys.stdin.readline()의 속도 차이가 크지 않습니다. 이 경우 어떤 것을 사용해도 무방합니다." 래.

밑에 효율적인 코드, 나랑 동일함;;

답글 달기