대학원생이 쉽게 설명해보기

N = int(input())

num_list = [1] * 10 # 0 ~ 9
num_list[0] = 0 # 0은 숫자가 아니므로

for i in range(1, N):
        temp = [0] * 10
        for j in range(10):
            if(j == 0): # 10, 101 과 같은 경우
                temp[1] += num_list[j] # 1이 나올 횟수
            elif(j == 9):
                temp[8] += num_list[j] # 8이 나올 횟수
            else:
                temp[j - 1] += num_list[j] # N이 2인 경우에, 첫자리가 1일 떄 0, 2 ; 2일 때 1, 3 이런 경우
                temp[j + 1] += num_list[j]

        num_list = temp
print(sum(num_list) % 1000000000)

import sys
N = int(input())
cnt_list = [0] * 10001

for i in range(N):
    cnt_list[int(input())] += 1

for i in range(10001):
    sys.stdout.write('%s\n' % i * cnt_list[i])

- 제출 시에는 input을 sys로 바꾸지 않으면 시간초과 뜰 가능성이 있음.(시도 안해봄)

- 여러 블로그에 카운팅 정렬을 위한 코드가 있지만, 메모리 초과 또는 시간 초과로 안되는 경우가 많음

- 이 문제의 핵심은 10001로 미리 배열의 크기를 지정해두고, 그 외에 값을 저장하지 않는다는 것.

- 배열이 1~2개만 늘어나도 메모리 초과가 뜨니 주의해야하는 문제

X = int(input())

dp = [X]
cnt = 0

while(True):
    if(1 in dp):
        print(cnt)
        break
    calc = []
    for i in dp:
        if(i % 2 == 0):
            calc.append(i / 2)
        if(i % 3 == 0):
            calc.append(i / 3)
        calc.append(i - 1)
    dp = calc

    cnt += 1

# 내가 푼건 dp방법이 아닌 것 같아 아래 코드를 붙임
# https://chunghyup.tistory.com/49 참고함
def min(x, y):
    return x if x <= y else y
 
x = int(input())
 
minimum_count = [0 for _ in range(x+1)]
 
index = 0
while(True):
    if index > x:
        break
 
    if index <= 1:
        minimum_count[index] = 0
    else:
        temp_min = x + 1
        if index % 3 == 0:
            temp_index = int(index/3)
            temp_min = min(temp_min, minimum_count[temp_index])
 
        if index % 2 == 0:
            temp_index = int(index/2)
            temp_min = min(temp_min, minimum_count[temp_index])
 
        temp_min = min(temp_min, minimum_count[index-1])
        minimum_count[index] = int(temp_min + 1)
    index = index + 1
    
print(minimum_count[x])

위의 코드는 0, 1 까지는 연산 횟수가 0이므로 일단 0을 채워준다.

미리 계산해놓은 인덱스(숫자 값)를 이용하여 최댓값을 구하는 방식.

점화식은 해당 리스트에서 min(/2, /3, -1) + 1이 된다. -> temp_min이 이 부분을 계산해주고 있음. 

마지막에 index = index + 1을 이용하여 점점 x값에 다가가게 됨.

* 재채점 후 정답 아님. 다시 풀어야 함.

N = int(input())
stair_score = [int(input()) for _ in range(N)]
dp = []

# init : for-loop에서 전칸 + 전전칸(i-3)의 경우를 생각하게 되므로
# 총 3개의 init값을 저장해 두어야 한다. 
# 1 : 첫 칸
# 2 : 첫 칸 + 다음 칸
# 3 : max(시작 위치 + 1칸 + 2칸의 경우, 2칸 + 한칸의 경우)
dp.append(stair_score[0])
dp.append(dp[0] + stair_score[1])
dp.append(max(dp[0] + stair_score[2], stair_score[1] + stair_score[2]))

for i in range(3, N):
    # 1 : 현재 위치에서 전칸을 밟아 올라온 경우 + 전전칸을 밟은 경우의 최댓값
    # 2 : 현재 위치 + 전전칸에서 올라온 경우
    dp.append(max(stair_score[i] + stair_score[i - 1] + dp[i - 3], stair_score[i] + dp[i - 2]))
print(dp[-1])

N = int(input())
triangle = [list(map(int, input().split())) for _ in range(N)]

# 총 N - 1번의 계산이 이루어진다.
for i in range(N - 1):
    for j in range(len(triangle[i + 1])):
        # 첫번쨰와 끝부분 같은 경우는 그냥 더해주면 된다.
        if(j == 0):
            triangle[i + 1][j] = triangle[i][j] + triangle[i + 1][j]
        elif(j == len(triangle[i + 1]) - 1):
            triangle[i + 1][-1] = triangle[i][-1] + triangle[i + 1][-1]
        # 그렇지 않고 중간에 있는 숫자들(예를 들어 1 3 1 의 3같은 경우)은 바로 위 그룹의 
        # 자기 자신의 인덱스 - 1 과 자기 자신의 인덱스와의 합이 총 2개가 나오는데
        # 2개 중 max를 고려하여 교체해야한다.
        else:
            triangle[i + 1][j] = max(triangle[i][j - 1] + triangle[i + 1][j], triangle[i][j] + triangle[i + 1][j])
print(max(triangle[-1]))