백준 algorithm study 2748 1904 9084 다이나믹 프로그래밍 DP python

파이썬 알고리즘 : 피보나치 수 2, 01타일, 동전

백준 2748, 백준 1904, 백준 9084

2023년 9월 7일 알고리즘 문제풀이

문제 1 백준 2748

문제 링크

1차 시도

나의 생각

기본적인 다이나믹 프로그래밍 문제였다. 재귀를 이용하면 시간초과가 되니 정의한 함수를 저장하는 배열을 만들어서 이를 참조하자.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import sys

n = int(sys.stdin.readline())

dp = [0 for _ in range(n+1)]
dp[1] = 1


def fibo(x):
    if x == 0:
        return dp[0]
    elif x == 1:
        return dp[1]
    else:
        if dp[x]:
            return dp[x]
        else:
            dp[x] = fibo(x-1) + fibo(x-2)
            return dp[x]


print(fibo(n))

문제 2 백준 1904

문제 링크

1차 시도

나의 생각

전 문제와 마찬가지였다. 그런데 계속 시간초과가 뜨길래 뭐가 문젠가 했는데 함수로 정의하지 않고 반복문을 사용해서 재귀를 타지 않았어야 했다. 오랜만에 푸는 다이나믹 프로그래밍이라..

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import sys

n = int(sys.stdin.readline())
sys.setrecursionlimit(10**9)
dp = [0 for _ in range(n+1)]
for x in range(1,n+1):
    if x == 1:
        dp[x] = 1
    elif x == 2:
        dp[x] = 2
    elif x == 3:
        dp[x] = 3
    else:
        dp[x] = (dp[x-1] + dp[x-2])%15746

print(dp[n])

문제 3 백준 9084

문제 링크

1차 시도

나의 생각

우선 각 동전과 같은 값을 가지는 경우는 무조건 1개는 존재한다. 예를 들어, 우리나라 동전일 경우 1원, 5원, 10원, 50원, 100원, 500원을 만드는 경우의 수는 최소 1가지는 존재한다. 여기서 각 동전을 뺸 값을 만드는 수를 모두 더해주었다. 예를 들어 1100원을 만드는 경우는

  • 1100-1 = 1099원을 만드는 경우
  • 1100-5 = 1095원을 만드는 경우
  • 1100-10 = 1090원을 만드는 경우
  • 1100-50 = 1050원을 만드는 경우
  • 1100-100 = 1000원을 만드는 경우
  • 1100-500 = 600원을 만드는 경우

위 경우를 모두 합한 값과 같다고 생각하여 코드를 작성하였지만 실패했다. 아직 감을 못잡은 것 같다.

결과

오답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    coins = list(map(int,sys.stdin.readline().split()))
    m = int(sys.stdin.readline())

    dp = [0 for _ in range(m+1)]
    for k in coins:
        dp[k] = 1
    for i in range(1,m+1):
        if i <= coins[0]:
            continue
        for j in range(len(coins)):
            if i - coins[j] >= 0:
                dp[i] += dp[i-coins[j]]
    print(dp[m])

2차 시도

나의 생각

우선 어떤 동전을 제거해서 생각해야 한다는 것은 맞는 접근이었다. 하지만 dp배열을 한번에 완성하려는게 내 문제였다. 어떤 값을 만드는 수는 내가 생각한 대로 모든 동전을 한번씩 빼봤을 때를 모두 합하면 되는 것이였다. 나는 어떤 값을 고정하고 뺼 동전을 순회하며 생각했었는데, 순서를 바꾸어 뺄 동전을 하나씩 고정한채로 모든 값을 순회하며 dp배열을 업데이트 해주었더니 생각보다 문제가 쉽게 풀렸다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    coins = list(map(int,sys.stdin.readline().split()))
    m = int(sys.stdin.readline())
    dp = [0 for _ in range(m+1)]

    for coin in coins:
        for i in range(m+1):
            if i == coin:
                dp[i] += 1
            elif i-coin > 0:
                dp[i] += dp[i-coin]

    print(dp[m])
CATALOG
    algorithm