해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 9461번  파도반 수열 - dp

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

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

풀이

1. 위와 같이 규칙을 찾아냅니다.
2. P[N] = P[N-3] + P[N-2] 구조의 피보나치 수열임을 알 수 있습니다.

전체코드

P = [0 for i in range(101)]
P[1] = 1
P[2] = 1
P[3] = 1
for i in range(4, 101):
    P[i] = P[i-3] + P[i-2]

t = int(input())
for i in range(t):
    n = int(input())
    print(P[n])

파이썬 / BOJ 백준 / 1904번 01타일 - dp

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

문제 

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.
그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

풀이 

1. 위와 같이 규칙을 찾아냅니다.
2. d[n] = d[n-2] + d[n-1] 구조의 피보나치 수열임을 알 수 있습니다.
3. 모든 2진 수열의 개수는 너무 큰 값을 가지고 있기 때문에, 문제의 출력에서 제시한 대로 15746을 나눈 나머지를 출력하도록 합니다.

전체코드

n = int(input())

dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for k in range(3,n+1):
    dp[k] = (dp[k-1]+ dp[k-2])%15746

print(dp[n])

파이썬 / BOJ 백준 / 9184번 신나는 함수 실행 - dp

문제

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
  1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
  w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
  w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)
a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

풀이

1. 문제에서 주어진 함수를 그대로 사용하면, 시간초과가 발생합니다.
2. 재귀함수를 사용할 때, 동일한 계산을 수행하지 않도록 메모이제이션을 사용하는 방법을 묻는 문제입니다.
3. 계산한 값을 dp[a][b][c]에 저장하고, 이후 a, b, c를 구할 때, 계산하지 않고, 저장한 dp[a][b][c]를 return하게 되면 수행시간이 기하급수적으로 단축됩니다.

전체코드

import sys

def w(a1,b1,c1):
    if dp[a1][b1][c1] != -1:
        return dp[a1][b1][c1]

    if a1 <= 0 or b1 <= 0 or c1 <= 0:
        dp[a1][b1][c1] = 1
        return dp[a1][b1][c1]
    if a1 > 20 or b1 > 20 or c1 > 20:
        dp[a1][b1][c1] = w(20, 20, 20)
        return dp[a1][b1][c1]
    if a1 < b1 and b1 < c1:
        dp[a1][b1][c1] = w(a1, b1, c1-1) + w(a1, b1-1, c1-1) - w(a1, b1-1, c1)
        return dp[a1][b1][c1]
    else :
        dp[a1][b1][c1] = w(a1-1, b1, c1) + w(a1-1, b1-1, c1) + w(a1-1, b1, c1-1) - w(a1-1, b1-1, c1-1)
        return dp[a1][b1][c1]

    pass

dp = [[[-1 for _ in range(n)] for _ in range(n)] for _ in range(n)]
while True:
    a,b,c = map(int, sys.stdin.readline().split())

    if a == -1 and b == -1 and c == -1:
        break

    result = w(a,b,c)
    p = f'w({a}, {b}, {c}) = {result}'
    print(p)