TIL # 33 : [Algorithm] 백준 / DP / Ascending Patterns

새해 알고리즘 스터디(1.1~7)

4일차

백준 문제 :
11057, 10844, 2579, 2156

{복습 1일차 1/7} DP와 빨리 친해지자...

---

DP 빡공 +4👩‍💻

DP 공부를 시작하는 마음가짐 🐳

◻️ 내 것이 될 때까지 물어보고 공부하고 정리하자
◻️ 파이써닉한 코드를 많이 보고 연구하자
◻️ 조급해 말고 나만 꽉 채우자

A) 11057번

로직 짜기:

** 무조건 오름차순이다.

길이 N, 또는 N자릿수에 해당하는 오르막 수를 구해야 한다. 그리고 N자리 구할 때 끝자리가 '3'이면 '3' 앞에 올 수 있는 수는 '3'보다 작거나 같은 값이다(0~3 숫자 허용). 그 후 해당 행의 값들을 모두 더하면 해당 행만큼의 자릿수를 가진 수의 가짓수가 나온다.

소스 코드:

import sys

N = int(sys.stdin.readline())
nums = [1] * 10
mod = 10007

for _ in range(N-1):
    for i in range(1, 10):
        nums[i] = (nums[i] + nums[i-1]) % mod

sys.stdout.write(str(sum(nums) % mod))

풀이:

2 자릿수를 놓고보면 :

• 0으로 끝나기 위해서는 이전수도 0일 수 밖에 없다 -> [00]
  즉 new_nums[0] = nums[0]이다.
• 1로 끝나기 위해서는 이전 수에 0,1이 올 수 있다 -> [01, 11]
  즉 new_nums[1] = nums[1] + nums[0] = nums[1] + new_nums[0]
• 2로 끝나기 위해서는 이전 수에 0, 1, 2가 올 수 있다 -> [02, 12, 22]
  즉 new_nums[2] = nums[2] + nums[1] + nums[0] = nums[2] + new_nums[1]
  ** 반복해서 풀면 new_nums[i] = new_nums[i - 1] + nums[i] 점화식을 구할 수 있다

풀이, 코드 출처 - suri78

풀이를 보고 그림으로 그려봤다.

1. 한 자릿수를 위해 nums를 [1, 1, 1, 1, ...]로 초기화한다
2. n자릿수-1만큼 순회한다.
3. 마지막수 [1-9]개를 순회한다(이미 한 자릴수는 nums에 추가돼있으니 1부터 시작한다)
4. 위에 나온 풀이 같이 nums[i] = (nums[i] + nums[i-1])로 설정하고 mod로 나눈다.
5. num에 저장된 값들을 모두 더하고 경우의 수를 출력한다.

문제풀이 체크리스트

◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

---

B) 10844번

로직 짜기:

인접한 모든 자리수의 차이는 1이며, 우리는 길이 N, 또는 N자릿수에 해당하는 계단수를 구해야 한다. 0으로 시작하는 수는 없고.. N은 1 <= N <= 100이다.

길이가 1인 경우:
이 문제에는 수가 0으로 시작할 수 없다고 명시돼 있다. 즉 [0]은 '1'이 아니라 '0' 값으로 저장된다. 나머지 수는 모두 1로 저장된다.
-> dp[i][j] = dp[i-1][j+1]
-> (2, 1) = (1, 1)

길이가 2~8인 경우:
10, 12, 21, 23, 32, 34, 43,...
-> dp[i-1][j+1] + dp[i-1][j-1]
-> (2, 3) = (1, 2) + (1, 4)

길이가 9인 경우:
-> dp[i][j] = dp[i-1][j-1]
-> (2, 9) = (1, 8)

1차 시도(실패):

# 계단수 입력
n = int(input())

# dp 테이블 만들기
dp = [[0]*10 for _ in range(100)]

# sum을 나눌 변수 선언
DIV = 1000000000

# dp[1]은 dp[1][0] 빼고 다 '1'로 만든다 
for i in range(1, 10):
    dp[1][i] = 1

# 2자리수 ~ 계단수까지 순회
for i in range(2, n + 1):
    # i자리수 + 마지막 숫자 순회
    for j in range(0, 10):
        # 마지막 숫자가 0이면
        if j == 0:
            # 마지막 숫자가 0일 때 +1 된다 -> 10, ...
            dp[i][j] = dp[i-1][j+1]
        # 마지막 숫자가 1<=j<=8
        if j >= 1 and j <= 8:
            # 마지막 숫자가 1<=j<=8일 때 +1, -1 된다 -> 21, 23, 32, 34 ...
            dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1]
        # 마지막 숫자가 9일 때
        else:
            # 마지막 숫자가 9일 때 -1 된다 -> 9, 89, ...
            dp[i][j] = dp[i-1][j-1]

# dp[n] 속 수를 다 더하고 DIV로 나눔
ADD = sum(dp[n])
print(ADD % DIV)

풀었으나 런타임 에러 나왔다ㅠㅠ

2,3차 시도(실패):

계속 런타임(IndexError)이 뜬다.. 휴

소스코드:

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(sum(dp[N]) % 1000000000)

출처 - titanumm

점화식만 같고 코드는 완전 다르다😭 소스코드가 훨씬 깔끔하고 전달력이 좋다.. 많이 보고 배우자!

문제풀이 체크리스트

◻️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◼️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

---

C) 2579번

규칙:

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 새의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

소스 코드:

N = int(input())
arr = [0]
dp = [0] * (N+1)
for _ in range(N):
    arr.append(int(input()))


for i in range(1, N+1):
    if i == 1:
        dp[i] = arr[1]
    elif i == 2:
        dp[i] = arr[1]+arr[2]
    else:
        dp[i] = max(dp[i-3]+arr[i-1]+arr[i], dp[i-2]+arr[i])

print(dp[N])

출처 - imacoolgirlyo

최댓값을 찾아야하는 문제이기 때문에 1번과 2번 중에서 더 큰 값을 dp[n] 안에 넣으면 된다.

출처 - 마이구미

문제풀이 체크리스트

◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

---

D) 2156번

규칙:

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

** 효주가 가장 많은 양의 포도주를 마실 수 있게 도와야 한다.

소스코드:

N = int(input())
wine = [0]
maxi = [0]*(N+1)
for i in range(1, N+1):
    wine.append(int(input()))
    if i < 3:
        maxi[i] = sum(wine)
    else:
        target = []
        target.append(maxi[i-3]+wine[i-1]+wine[i])
        target.append(maxi[i-2]+wine[i])
        target.append(maxi[i-1])
        maxi[i] = max(target)
print(maxi[-1])

출처 - 개발로그

1. i-1번째와 i-2번째 둘 다 마신 경우 = i번째 위치를 마실 수 없다 --> table[i-1]
2. i-1을 마시지 않은 경우 = table[i-2] + arr[i]
3. i-2를 마시지 않은 경우 = table[i-3] + arr[i-1] + arr[i]

출처 - 인스피릿

문제풀이 체크리스트

◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

---

Reference
https://www.acmicpc.net/
https://suri78.tistory.com/92
https://mygumi.tistory.com/260
https://velog.io/@imacoolgirlyo/2579%EB%B2%88-%EA%B3%84%EB%8B%A8-%EC%98%A4%EB%A5%B4%EA%B8%B0-5dk4m8to5f
https://mygumi.tistory.com/100
https://titanumm.tistory.com/85
https://in0-pro.tistory.com/26
https://m.post.naver.com/viewer/postView.nhn?volumeNo=29414982&memberNo=33264526