10844 - 쉬운 계단 수

쉽지않은 문제였습니다.

일단 위와같이 각 자릿수의 차이가 1인 수를 게단수라고 할 때, 자릿수가 주어지면 해당 자릿수에서 가능한 계단 수의 경우의 수의 합을 출력하면 되는 문제입니다.

---

분석

이 문제가 어려운 이유로는 두 가지가 있습니다.

일단 첫번째로 규칙이 까다로워서 점화식 세우는 거 자체가 쉽지 않다는 거고, 두 번째로 점화식을 두 경우로 나누어서 생각해봐야 한다는 점입니다.

일단 첫번째 경우는 위와 같이 N으로 시작하는 계단 수의 경우의 수를 나열해봤을 때 처음에 보고 어? 이거

dp[i][j] = dp[i-1][j] + dp[i-1][j+1]인가? 또는
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]인가 싶었습니다.

한마디로 현재 조사중인 경우는 이전 자릿수의 인덱스 -1이거나 +1이라고 생각했습니다.

그러나 두 경우 다 오답이 나옵니다.

해당 문제는 그림의 하늘/초록 형광펜처럼 점화식을 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이라는 위 상대각선 형태로 찾아야 풀이가 가능합니다. 덧붙여서 상대각선 형태여야지만 0번 인덱스를 조사할 때 (파이썬의 경우입니다) -1과 1을 참조하여 점화식으로 0번째 인덱스를 정상적으로 참조하는게 가능합니다.

두 번째 경우는 9로 시작하는 계단 수의 경우입니다.
계단 수가 9로 시작하게 되면 다른 점화식이 적용되지 않습니다.

처음에는 dp[i][j-1]을 참조하면 해결될까 싶었는데 역시 아니었습니다. 이 경우에는 그림의 노란 형광펜처럼 상 좌대각선의 수를 가져다 써야 정상적인 점화식이 가능합니다.

---

코딩

N = int(input())
dp = [[0]*9 for _ in range(N)]
for first in range(9):
    dp[0][first] = 1

dp배열을 만들어주고 첫번째 리스트는 다 1로 초기화해주겠습니다.

for i in range(1,N):
    for j in range(9):

2번째 리스트부터 1~N까지의 자릿수마다 0~8로 시작하는 계단 수의 경우를 대입하겠습니다.

        if j==8:
            dp[i][j] = dp[i-1][j-1]

위에 분석한대로 현재 9로 시작하는 계단 수의 경우의 수를 대입해주려면 상 좌대각선의 숫자를 기입해줍시다.

        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

그 경우가 아니라면 상 좌우대각선의 수를 하나씩 뽑아 더한 값을 현재 계단 수의 경우의 수에 넣어주면 됩니다.

print(sum(dp[N-1])%1000000000)

마지막으로 문제 조건대로 해당 자릿수의 계단 수의 합산에 10억을 나눈 나머지를 출력하면 됩니다.

---

---

1932번 - 정수 삼각형

아래로 내려오면서 대각선으로 값을 합산할 수 있는데 최종적으로 내려왔을 때 가장 큰 값이 되는 수를 구하면 되는 문제입니다.

import copy
N = int(input())
lst = []
for _ in range(N):
    lst.append(list(map(int,input().split())))
dp = copy.deepcopy(lst)

일단 저 정수삼각형을 리스트로써 받고 DP 기록을 하기 위해 리스트를 deepcopy 해주겠습니다.

for i in range(len(dp)-1):
    for j in range(len(dp[i])):

그리고 위에서부터 끝-1 까지 합산을 위해 리스트를 순회하겠습니다.

        if lst[i+1][j] + dp[i][j] > dp[i+1][j]:
            dp[i+1][j] = lst[i+1][j] + dp[i][j]

첫 번째 경우부터 살펴보겠습니다.
현재 DP에는 나올 수 있는 최대값이 기록되어있다고 가정해야합니다.

바로 아래 있는 값 + 현재까지 기록된 최대값 이 바로 아래 기록될 최댓값보다 크다면
바로 아래 기록될 최댓값 = 바로 아래 있는 값 + 현재까지 기록된 최대값으로 표기해줍시다.

        if lst[i+1][j+1] + dp[i][j] > dp[i+1][j+1]:
            dp[i+1][j+1] = lst[i+1][j+1] + dp[i][j]

피라미드는 양 대각선 방향이므로 오른쪽에 있는 인덱스 하나 더 코딩해주시면 됩니다.

print(max(dp[-1]))

마지막으로 가장 아랫 값에서 가장 큰 값이 나올 수 있는 최대 경우의 수이므로 출력하시면 됩니다.

---

---