Carpe Diem Carpe Diem

DP로 푼다고 하는데 그냥 단순 구현으로 푼 것 같다... n=int(input()) # 5 = 1/1/1/1/1 # 5 = 3/1/1/ cnt=0 while n!=0: if n>=3: n-=3 else: n-=1 cnt+=1 if cnt%2==0: print("CY") else: print("SK") 3개 이상 남아있으면 3개를 가져가고 그렇지 않으면 1개를 가져가는 방식으로 구현하였다. 어짜피 어떻게 가져가던간에 마지막에 가져가는 사람은 똑같기 때문..!

처음에는 조합? 확률과 통계 공식으로 풀어보려했는데 생각해보니 그렇게 복잡하게 풀 필요가 없었다. 테두리를 1로 초기화하고 puddle이 있는 좌표는 0으로 하여 dp[i][j]=dp[i-1][j]+dp[i][j-1] 을 사용해 풀면 되는 것이었다! def solution(m, n, puddles): dp=[[1]*n for _ in range(m)] for p in puddles: dp[p[0]-1][p[1]-1]=0 for i in range(1,m): for j in range(1,n): if dp[i][j]!=0: dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007 return dp[m-1][n-1] 처음에는 puddle 위치를 0으로 만들고 dp 적용하면 되겠다 싶었는..

N=7, M=7일때 dp[i]와 dp[i-day]+page 중 더 큰 값을 dp[i]에 넣는다! (day,page) 0 1 2 3 4 5 6 7 (2,200) 0 0 200 200 200 200 200 200 (4,40) 0 0 200 200 200 200 240 240 (5,20) 0 0 200 200 200 200 240 240 (1,20) 0 20 200 220 220 220 240 260 (2,15) 0 20 200 220 220 235 240 260 (3,10) 0 20 200 220 220 235 240 260 (1,10) 0 20 200 220 230 235 245 260 n,m=map(int,input().split()) bag=[] for i in range(m): day,page=map..

0-1 Kanpsack 알고리즘 배낭문제: 일정한 가치와 무게가 정해져있는 짐들을 배낭에 담을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 가방의 가치: value 가방의 무게: weight 최대이윤=dp[n]이라고 할때 dp[i]=max(dp[i],dp[i-weight]+value) 129865 평범한 배낭 n,k=map(int,input().split()) bag=[] for i in range(n): w,v=map(int,input().split()) bag.append((w,v)) bag.sort(key=lambda x:x[1]) dp = [0]*(k+1) for w, v in bag: for i in range(k, w-1, -1): dp[i] = max(dp[i], dp[i-..

pypy3로 해야지 통과됨 import sys from collections import deque n=int(sys.stdin.readline()) queue=deque() queue.append([n]) result=[] while queue: q=queue.popleft() i=q[0] if i==1: result=q break if i%3==0: queue.append([i//3]+q) if i%2==0: queue.append([i//2]+q) queue.append([i-1]+q) print(len(result)-1) result.reverse() print(*result)

첫 풀이(시간초과....) def stair(num): num=list(map(int,str(num))) for i in range(1,len(num)): k=abs(num[i]-num[i-1]) if k!=1: return False return True count=0 for i in range(10**(n-1),10**n): if stair(i)==True: count+=1 print(count) 정답(인터넷 참고함...) import sys n=int(sys.stdin.readline()) dp=[[0]*10 for _ in range(n+1)] for i in range(1,10):#n이 1일때 (한자리 수일때) dp[1][i]=1 #1~9 모두 계단수 for i in range(2,n+1): #..

def solution(n): dp=[0]*(n+2) dp[2]=3 for i in range(4,n+1,2): dp[i]+=(dp[i-2]*3)+2 for j in range(2,i-2,2): dp[i]+=dp[j]*2 dp[i]=dp[i]%1000000007 return dp[n] #0:0 #2:3=3 #4:11=9+2 #6:41=33+6+2 #8:153=123+22+6+2=dp[6]*3+dp[4]*2+dp[2]*2+2

import sys t=int(sys.stdin.readline()) dp=[0]*10001 dp[1]=1 dp[2]=2 dp[3]=3 for i in range(t): n=int(sys.stdin.readline()) for j in range(4,n+1): dp[j]=(j//2)+1+dp[j-3] print(dp[n]) #n=1일때: 1 ->1개 #n=2일때: 2 , 11 ->2개 #n=3일때: 111,12,3 ->3개 #n=4일때: 1111,112,22,31 ->4개=3+f(1) #n=5일때: 11111,1112,122, 113, 23 -> 5개=3+f(2) #n=6일때: 111111,11112,1122,123,1113,222,33 ->7개=4+f(3) #n=7일때 -> 8개=4+f(4) #n=8일..