스칼렛의 코딩라이프

문제 풀기 전에는 계단 오르기와 비슷할거라고 생각했다. 근데 N=int(input()) wl=[int(input()) for _ in range(N)] dp=[0]*N dp[0]=wl[0] if N>1: dp[1]=wl[0]+wl[1] if N>2: dp[2]=max(wl[0]+wl[2],wl[1]+wl[2],dp[1]) for i in range(3,N): dp[i]=max(dp[i-2]+wl[i],wl[i]+wl[i-1]+dp[i-3],dp[i-1]) print(dp[N-1]) 근데 너무 꼬아서 생각했나..?,, 막 이리저리 꼬아서 생각하다가 머리 속이 엉켜버렸다. 계단오르기는 현재 밟고 있는 계단의 점수를 무조건 더해야 했지만, 포도주시식 문제는 패스 할 수도 있다는게 다른 점 같다.

하루 종일 푼 것 같다. 결국 엑셀로 5자리수 까지 해 보고 풀 수 있었던.. 노가다의 산물 근데 이 전에 있었던 정수삼각형이나 RGB거리와 비슷한 문제인 것 같다는 생각이 들었다. N=int(input()) dp=[[0 for _ in range(10)] for _ in range(N+1)] dp[1]=[0,1,1,1,1,1,1,1,1,1] for i in range(2,N+1): for j in range(10): if j==0: dp[i][j]=dp[i-1][1] elif j==9: dp[i][j]=dp[i-1][8] else: dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%1000000000 sdp=sum(dp[N])%1000000000 print(sdp) 뭔가 내 힘으로 푼 ..

해도.. 해도.. 해도해도.. 동적계획법 풀이를 보면 아..! 하는데 왜 나는 구현을 못 하는 것이지... dp의 인자값을 N값으로 둘 생각 조차 못했다.. 그냥 연산 한 다음에 중복 빼고 거기서 있나 찾아보기..로 생각했는데 아무리 생각해도 메모이제이션을 쓸 만한게 없다 했더니 휴.. 언제쯤 구글링 없이 내 힘으로 문제를 풀 수 있을까.. N=int(input()) dp=[0]*(N+1) for i in range(2,N+1): dp[i]=dp[i-1]+1 if i%3==0: dp[i]=min(dp[i],dp[i//3]+1) if i%2==0: dp[i]=min(dp[i],dp[i//2]+1) print(dp[N])

동적계획법,, 아 알았다! 싶으면 또 아니고 ... 아직까지 여러 유형을 공부한다고 생각하고 해야되는데 너무 어렵다 ㅜㅜ.. 결국 다른 분 풀이 보고 했는데, "합" 이라는 말에 계속 점화식을 찾으면서 어떤 최댓값을 더해서 해야할지 찾고 있었는데 아하하 최대값,,,max,,max로 찾으면 되는것을,, N=int(input()) nl=[0 for _ in range(301)] for i in range(N): nl[i]=int(input()) dp=[0 for _ in range(301)] dp[0]=nl[0] dp[1]=nl[0]+nl[1] dp[2]=max(nl[0]+nl[2],nl[1]+nl[2]) for i in range(3,N): dp[i]=max(dp[i-2]+nl[i],dp[i-3]+nl[i..

정수삼각형.. 최댓값을 저장하면서 내려오기 N=int(input()) tlist=[list(map(int,input().split())) for _ in range(N)] k=2 for i in range(1,N): for j in range(k): if j==0: tlist[i][j]=tlist[i][j]+tlist[i-1][j] elif i==j: tlist[i][j]=tlist[i][j]+tlist[i-1][j-1] else: tlist[i][j]=max(tlist[i-1][j-1],tlist[i-1][j])+tlist[i][j] k+=1 print(max(tlist[N-1]))

동적계획법,, 이젠 익숙해졌다고 생각했는데, 전혀 아니었다.. N=int(input()) RGB=[list(map(int,input().split())) for _ in range(N)] for i in range(1,N): RGB[i][0]=min(RGB[i-1][1],RGB[i-1][2])+RGB[i][0] RGB[i][1]=min(RGB[i-1][0],RGB[i-1][2])+RGB[i][1] RGB[i][2]=min(RGB[i-1][0],RGB[i-1][1])+RGB[i][2] print(min(RGB[N-1])) 그 전까지는 다른 리스트에 값을 저장해서 불러오는 방식으로 했는데, 이번에는 값 자체를 누적해서 저장하는 방식.. 전혀 감이 안잡혀서 다른 분 풀이를 참고했다.. 아직도 갈 길이 멀었다..