Carpe Diem Carpe Diem

2xn 타일링2를 먼저 풀고 풀어서 그런지 쉬웠다. n=int(input()) dp=[0]*(n+2) dp[1]=1 dp[2]=2 if n>=3: for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2] print(dp[n]%10007) #피보나치 수열과 식이 같음 # dp[1]=1 # dp[2]=2 # dp[3]=3 # dp[4]=5

dp문제를 여러개 풀다 보니 감이 잡히는 것 같기도.. t=int(input()) for i in range(t): n=int(input()) dp=[0]*(n+3) dp[0]=dp[1]=dp[2]=1 if n>=3: for j in range(3,n): dp[j]=dp[j-2]+dp[j-3] print(dp[n-1])

DFS, BFS 문제 구분하는 방법 그래프의 모든 정점을 방문 -> DFS, BFS 모든 노드를 방문, 경로의 특징을 저장, 미로탐색을 진행하는데, 이동할 때마다 가중치가 붙어서 이동 -> DFS 최단거리 구하기, 미로 탐색(최단 거리만을 가지고 탈출) -> BFS def dfs(graph,v,visited): visited[v]=True # print(v,end=' ') for i in range(n+1): if graph[v][i]==1 and not visited[i]: dfs(graph,i,visited) n=int(input()) #컴퓨터 개수 connected=int(input()) #연결된 쌍의 개수 graph=[[0]*(n+1) for _ in range(n+1)] visited=[Fals..

dp 문제를 풀 때마다 느끼는 거지만 점화식을 찾는게 중요한 것 같다. import sys n=int(sys.stdin.readline()) dp=[0]*(n+2) dp[1]=1 dp[2]=3 if n>=3: for i in range(3,n+1): dp[i]=dp[i-1]+2*dp[i-2] print(dp[n]%10007) # 1: 2*1 -> 1가지 # 2: 2*2 -> 3가지 # 3: 2*3 -> 5가지 (3+1*2) # 4: 2*4 -> 11가지 (5+3*2) # 5: 2*5 -> 21가지 (11+5*2) # 6: (21+22)=43 # 7: 43+42=85 # 8: 85+86=171

알몸을 제외한 모든 조합의 개수를 구하는 것이다. 공식을 옛날에 배웠었는데 공식을 모르면 못풀었을듯.... import sys from collections import defaultdict t=int(sys.stdin.readline()) for i in range(t): cloth_set=defaultdict(list) sum=1 n=int(sys.stdin.readline()) for j in range(n): cloth_name,cloth_kind=sys.stdin.readline().split() cloth_set[cloth_kind].append(cloth_name) for key in cloth_set: sum*=(len(cloth_set[key])+1) #각 옷 종류마다 (옷이름의 개수+1..

n>=4부터 f(n)=f(n-1)+f(n-2)+f(n-3)이라는 규칙을 찾아내는 것이 관건 import sys t=int(sys.stdin.readline()) dp=[0,1,2,4,0,0,0,0,0,0,0,0] for i in range(t): n=int(sys.stdin.readline()) for j in range(4,n+1): dp[j]=dp[j-1]+dp[j-2]+dp[j-3] print(dp[n]) #n=1일때: 1 ->1개 #n=2일때: 2 , 11 ->2개 #n=3일때: 111,12(2),3 ->4개 #n=4일때: 1111,112(3),22,31(2) ->7개 #n=5일때: 11111,1112(4),122(3),23(2),113(3) -> 13개 #n=6일때: 111111,11112(5)..

indexerror을 못찾아서 한시간동안 헤맸다.... import sys n=int(sys.stdin.readline()) dp_in=[0]*(n+1) for i in range(n): k=int(sys.stdin.readline().rstrip()) dp_in[i]=k # dp_in =10 20 15 25 10 20 dp=[0]*(n+1) dp[0]=dp_in[0] dp[1]=dp_in[0]+dp_in[1] if n>=2: #n=1이면 indexerror 뜸 if문 설정 안해줘서 error 뜸 dp[2]=max(dp_in[0]+dp_in[2],dp_in[1]+dp_in[2]) # 초기화 dp=10, 30, 35, 0, 0, 0 for j in range(3,n): dp[j]=max(dp_in[j]+d..

import sys n,m=map(int,sys.stdin.readline().split()) pocketmon={} pocketmon2={} for i in range(1,n+1): eng=sys.stdin.readline().rstrip() pocketmon[i]=eng pocketmon2[eng]=i for j in range(m): find=sys.stdin.readline().rstrip() if find.isdigit(): print(pocketmon[int(find)]) else: print(pocketmon2[find])