해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 2156 포도주 시식 - dp

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

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

풀이

1. dp로 풀 수 있는 문제입니다.
2. 각 계단의 점수는 입력을 받아와 리스트 s에 넣습니다. (s[0]을 첫번째 잔으로 생각합니다.)
1차원 dp를 만들고, dp의 첫번째에는 s[0]을 넣습니다.
두번째 잔은 첫번째 잔을 마시고, 두번째 잔을 마시는 것이 최대이기 때문에 dp의 두번째에는 s[0] + s[1]을 넣어줍니다.

3. dp[n]은 직전 잔을 마시는 경우와, 전전 잔을 마시는 경우가 있습니다. 이 두가지 경우의 최대값을 넣어줍니다. 그러면 dp에는 각 층까지의 최대값이 누적되어 들어가게 됩니다.

4. 직전 잔을 마시는 경우 (n-1)는 전전 잔(n-2)을 마실 수 없으니, 그 전 잔(n-3)을 마실 수 있습니다. 식으로 만들면 dp[n-3] + s[i-1]로 표현할 수 있습니다.

5. 전전 잔을 마시는 경우는 dp[n-2]로 표현할 수 있습니다.

6. 이를 식으로 만들면 dp[i] = max(dp[i - 3] + s[i - 1] , dp[i - 2]) + s[i]로 표현할 수 있습니다.

전체 코드

n = int(input())
dp = [0] * 10002
s  = [0] * 10002

for i in range(1, n + 1):
    s[i] = int(input())

dp[1] = s[1]
dp[2] = s[1] + s[2]

for i in range(3, n + 1):
    dp[i] =max(dp[i - 1], dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i])
print(dp[n])

파이썬 / BOJ 백준 / 10844번 쉬운 계단 수 - dp

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

문제

45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

풀이

1. DP(동적계획법)을 이용해 풀 수 있는 문제입니다. DP테이블은 이차원 리스트이며 DP[자리 수][앞에 오는 숫자]=경우의 수로 표현합니다.

2. 앞에 오는 숫자 = 0이면 아래와 같은 식으로 표현합니다. 0 다음에는 1밖에 올 수 없습니다. 

DP[자리 수][0] = DP[자리 수 - 1][1]

맨앞에는 0이 올수 없고, 그 아래 자리수부터는 0이 올 수 있으니, 맞교환하는 식으로 하여, 간단하게 식을 만듭니다.

 3. 앞에 오는 숫자 = 1~8 이면 아래와 같은 식으로 표현합니다. 1 ~ 8은 각각 2개씩 올 수 있습니다. 

DP[자리 수][앞에 오는 숫자] = DP[자리 수 - 1][앞에 오는 숫자 -1] + DP[자리 수 - 1][앞에 오는 숫자 + 1]

 4. 앞에 오는 숫자 = 9이면 아래와 같은 식으로 표현합니다.

DP[자리 수][9] = DP[자리 수 - 1][8]

5. 마지막에 DP[자리수]에 있는 값을 모두 더하고, 1000000000의 나머지를 구해줍니다.

전체 코드

n = int(input())
dp = [[0 for i in range(10)] for j in range(101)]
for i in range(1, 10):
    dp[1][i] = 1
for i in range(2, n + 1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i - 1][1]
        elif j == 9:
            dp[i][j] = dp[i - 1][8]
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
    #print(dp[i])
print(sum(dp[n]) % 1000000000)

파이썬 / 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)