n = int(input()) d = [0] * 1001 d[1], d[2] = 1, 2 for i in range(3, n+1): d[i] = d[i-1] + d[i-2] print(d[n]%10007) 일반적인 dp문제로 점화식을 세워야 한다. 잘 생각하고 항상 점화식을 세우자. 이건 기본적인 문제 유형이다. N의 길이가 1일때는 경우의 수가 1, 2일때는 경우의 수가 2, 3일때는 3, 4일때는 5, 5일때는 8이다. 이는 1의 길이와 2의 길이를 가진 타일을 n-1의 길이일 때와 n-2의 길이일 경우 두 가지가 있다는 것을 기반으로 3부터는 이 두 가지 경우가 합쳐진 경우의 수가 정답이 되는 것이다. 그래서 점화식이 n = n-1의 경우의 수 + n-2의 경우의 수가 된다는 것을 알 수 있다.

n = int(input()) d = [0] * (n + 1) for i in range(2, n + 1): d[i] = d[i - 1] + 1 if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) print(d[n]) 일단 dp에는 2부터 시작하여 2에서 일을 뺀 수인 1이 들어가야한다. 그 값은 원래 모두 0인 인덱스에서 dp[2-1]인 값에 +1을 하여 들어가게 되고 이후부터는 그 전 값에 1이 더해진 값이 들어가게 된다. 즉 2 인덱스는 1, 3 인덱스는 2, 4 인덱스는 3인 형식이다. 이후 만약 i 가 3으로 나누어진다면 3으로 나누어진 인덱스의 값에 나누기를 실행한 값인 1을 더..

A, P = map(int, input().split()) dp = [A] same = 0 while same == 0: num = 0 for j in str(dp[-1]): num += int(j)**P if num in dp: same = num break dp.append(num) print(dp.index(same)) 간단하게 스택의 가장 위 값을 문자열로 변경하고 각 자리 수마다 p만큼 제곱해준 값을 더한 변수를 스택에 추가한다. 만약 동일한 값이 이미 스택에 있다면 반복문을 멈추고 그 값의 인덱스를 찾아주면 해결된다.

N = int(input()) def sol(n): if n == 1: return 1 elif n == 2: return 2 elif n == 3: return 4 else: return sol(n-1) + sol(n-2) + sol(n-3) for i in range(N): n = int(input()) print(sol(n)) 1 = 1/ 2 = 2/ 3 = 4/ 4 = 7/ 5 = 13 위의 값은 경우의 수 이며 4와 5를 보면 해당 값들이 전의 값 3개의 더한 것임을 알 수 있다. 그러므로 점화식을 세워서 풀어 재귀로 풀었으나 하향식을 이용하여 배열에 값을 넣어두는 방식도 얼마든지 이용할 수 있다. T = int(input()) for i in range(T) : n = int(input()) ..

import sys sys.setrecursionlimit(10**7) def dfs(x, sig): sig[x] = True if sig[cycle[x]] == False: dfs(cycle[x], sig) for i in range(int(input())): N = int(input()) cycle = [0] + list(map(int,input().split())) sig = [False] * (N+1) ans = 0 for i in range(1, len(cycle)): if sig[i] == False: dfs(cycle[i], sig) ans +=1 print(ans) 재귀에 대한 제한을 풀어주는게 포인트이며 bfs로도 풀이가 가능하지만 직관적인 dfs를 택했다. 해당 문제는 인덱스와 그 안의..

HTML 삽입 미리보기할 수 없는 소스 def solution(n, lost, reserve): lost_ = [r for r in lost if r not in reserve] reserve_ = [l for l in reserve if l not in lost] # 반복문을 이용한 중복 제거 넣을 인자, 반복문, 조건문 순으로 들어간다. lost_.sort() reserve_.sort() # 효율적인 코드를 위해서 오름차순 정렬 for i in reserve_: # 오름차순으로 정렬했기에 빼기부터 검열 if i-1 in lost_: lost_.remove(i-1) elif i+1 in lost_: lost_.remove(i+1) return n - len(lost_)