1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 메모이제이션과 점화식 그리고 max를 사용하면 되겠거니 했는데 max를 어떻게 적용해야할지 떠올리지못했다. 그리고 for문은 왜 하나만 쓰는거에 꽂혀서 이중포문으로 생각을 안했다. 첫번째 풀이 - 틀림 dp를 초기화하고 상자에 들어갈수있다면 1씩 늘려줬는데 1씩 늘려서 그런지 느릴 것이고 그래서 틀린 것 같다. n = int(input()) box = list(map(int,input().split())) dp=[0]*1001 for i in range(n): for j..

www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net dp=[0]*n 으로 하면 런타임에러 n = int(input()) dp = [0]*81 dp[0]=1 dp[1]=1 for i in range(2,n): dp[i] = dp[i-1]+dp[i-2] r = dp[n-1] + dp[n-1] + dp[n-2] print( r+r ) 근거 있는 이유를 만들자

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 DP의 가장 대표적인? 예제 같다. 외우듯이 알아두자 # 1463번 1로 만들기 n = int(input()) dp = [0 for _ in range(n+1)] for i in range(2,n+1): dp[i]=dp[i-1]+1 if i%3 ==0 and dp[i//3]+1

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속합을 스터디때 설명을 약간 들어서 그런지 거기서 얻은 아이디어로 문제를 풀었는데 맨땅에 헤딩식으로 풀었으면 못풀었을 것 같다. DP에서 생명은 점화식을 떠올릴 수 있느냐 없느냐다! (and 항상 저장을 하는 cache 공간이 필요) n = int(input()) arr = list(map(int,input().split())) dp = [0 for _ in range(n+1)] dp[0]=arr[0] for i in ..

www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 풀이1 - 시간초과 문제 읽고 어떤 유형인지 파악안하고 생각나는 대로 풀었다. 제출해보니 시간초과가 나왔고 유형으로 접근해봐야겠다는 생각이 들었다. #9625번 BABBA tmp='A' k= int(input()) for i in range(k): new_tmp='' for j in tmp: if j=='A': new_tmp+='B' elif j=='B': new_tmp+='BA' tmp=new_tmp cnt_A=..

www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net 풀이1 - 메모이제이션 없는 재귀 - 시간초과 직관적으로 문제보고 짜봤는데 메모이제이션을 적용하지않아 시간초과 날 것 같았는데 돌려보니 시간초과가 났다 . 재귀 쓸거면 메모이제이션 적용해서 쓰자 t = int(input()) def koong(n): if n