백준 2775 : 부녀회장이 될거야

t = int(input())

for _ in range(t):
    k = int(input())  # 층
    n= int(input())  # 호
    f0 = [x for x in range(1, n+1)]  # 0층 리스트
    for k in range(k):  # 층 수 만큼 반복
        for i in range(1, n):  # 1 ~ n-1까지 (인덱스로 사용)
            f0[i] += f0[i-1]  # 층별 각 호실의 사람 수를 변경
    print(f0[-1])  # 가장 마지막 수 출력

• 참고한 코드

접근방식

후기

문제를 풀어보니 재귀로 푸는 방법이 먼저 생각나 전체적인 이해는 되었는데 오류가 나서 코드를 참고하였다.

• 추가 후기 :다이나믹이 뭐예요 문제를 풀고 나니 2차배열로 접근해서 푸는 방법도 가능할거 같다고 생각했다.

백준 2748 : 피보나치 수 2

def fibo(n):
    if n == 1 or n == 2:
        return 1
    else:
        if memorization[n] != 0:
            return memorization[n]
        else:
            memorization[n] = fibo(n-1)+ fibo(n-2)
            return memorization[n]

if __name__ == "__main__":
    num = 5
    memorization = [0] * (num+1)
    print(fibo(num))

후기

top_down 방식은 맞고 bottom_down은 런타임 에러가 났다..
무엇때문에 런타임이 났는지 다시 확인해보아야겠다.

백준 14494 : 다이나믹이 뭐예요?

n, m = map(int, input().split())
dp = [[0]*(m+1) for _ in range(n+1)]
dp[1][1] = 1
for y in range(1, n+1):
    for x in range(1, m+1):
        dx = x+1
        dy = y+1
        if 0<dx<=m:
            dp[y][dx] += dp[y][x]
        if 0<dy<=n:
            dp[dy][x] += dp[y][x]
        if 0<dx<=m and 0<dy<=n:
            dp[dy][dx] += dp[y][x]
print(dp[-1][-1]%1000000007)

접근 방식

후기

알고리즘 수업에서 했던 최단경로 문제와 비슷하다.
근데 까먹었다..ㅎㅎ

백준 1463 : 1로 만들기

x=int(input()) # 수 입력받기
d=[0]*(x+1) # 1-based
for i in range(2,x+1): # 2부터 x까지 반복
    d[i]=d[i-1]+1 # 1을 빼는 연산 -> 1회 진행
    if i%2==0: # 2로 나누어 떨어질 때, 2로 나누는 연산
        d[i]=min(d[i],d[i//2]+1)
    if i%3==0: # 3으로 나누어 떨어질 때, 3으로 나누는 연산
        d[i]=min(d[i],d[i//3]+1)
print(d[x])

접근 방식

후기

2의 배수이거나 3의 배수이라면 2의 연산횟수, 3의 연산횟수에 더하는 방식으로 접근, 2또는 3의 배수가 아니면 n-1하여 n-1의 연산횟수에 횟수 1 추가(1 빼기 연산 횟수 추가)

백준 1562 : 계단 수

후기

골드는 너무 어려워..