본문 바로가기

전체 글111

[이코테] 다이나믹 프로그래밍 - 금광 다이나믹 프로그래밍은... 모르겠다... 오늘도 못 풀었다 1-1. 풀이 도중 생각 1) 입력을 2차원으로 변환해주는 코드를 익혀야겠다 2) maz(오른쪽 아래, 오른쪽, 오른쪽 위)로 하면 될 것 같은데 2. 책 풀이 for tc in range(int(input())): # 금광 정보 입력 n, m = map(int, input().split()) array = list(map(int, input().split())) # 다이나믹 프로그래밍을 위한 2차원 dp 테이블 초기화 dp =[] index = 0 for i in range(n): dp.append(array[index:index + m]) index += m # 다이나믹 프로그래밍 진행 for j in range(1, m): for i in .. 2023. 2. 25.
[이코테] 다이나믹 프로그래밍 - 바닥 공사 오랜만에 아예 감을 못 잡겠는 문제였다 1-1. 풀이 도중 생각 1) 주어진 조건이 무조건 2xN인 모양이라 그나마 생각이라도 좀 했는데, 아니었으면 아예 접근도 못했을듯 2) N이 짝수라면 2x1 블록이 없어도 괜찮고 N이 홀수라면 2x1 블록은 무조건 하나 있어야 한다 3) 그 뭐냐 sliding window처럼 슈슉 지나가면서 만들어내는 규칙 같은게 있을 것 같은데 모르겠다 4) 결과를 769,769로 나눈 나머지를 출력하라고 하는데 특이하다 2. 책 풀이 아니 이거 점화식 세우는거 어떻게 생각하는거임????? i-1번째, i-2번째 이런 패턴으로 생각하는 것 같은데 n = int(input()) d = [0] * 1001 # 다이나믹 프로그래밍 진행 (바텀업) d[1] = 1 d[2] = 3 fo.. 2023. 2. 23.
[이코테] 다이나믹 프로그래밍 - 개미 전사 1. 내 풀이 n = int(input()) k = list(map(int, input().split())) dp = [0]*1002 result = 0 for j in range(n): dp[j] = k[j] for i in range(3, n+2): dp[i] = max((dp[i] + dp[i-2]), (dp[i] + dp[i-3])) print(dp) print(max(dp[n-2], dp[n-1])) 1-1. 풀이 도중 생각 1) 점화식을 차근차근 생각해보자 2) 결국 a_{n+2}와 a_{n+3} 값 중 최대가 되는 식을 선택해가면 될 것 같다 3) 처음엔 dp 테이블과 k 를 둘 다 사용하는 방식으로 코드를 짰는데, 그러면 값이 누적합산이 안 되어 k를 버리고 dp 테이블만 이용 2. 책 풀.. 2023. 2. 22.
[이코테] 다이나믹 프로그래밍 - 1로 만들기 정답을 봐도 이걸 내가 생각해낼 수 있었을까 의문이 드는... 점화식 세워보는 걸 좀 연습해야 하나 싶기도 하고 1. 내 풀이 d = [0] * 30000 x = int(input()) def cal_cnt(x): if x == 1: return None elif x % 5 == 0: x //= 5 d[x] = 1 return cal_cnt(x) elif x % 3 == 0: x //= 3 d[x] = 1 return cal_cnt(x) elif x % 2 == 0: x //= 2 d[x] = 1 return cal_cnt(x) elif (x % 5 != 0) and (x % 3 != 0) and (x % 2 != 0): x -= 1 d[x] = 1 return cal_cnt(x) cal_cnt(x) p.. 2023. 2. 21.

티스토리툴바