CS/알고리즘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. [이코테] 실패율 뭔가 알 것 같은데 못 푸는 느낌 1. 내 풀이 ㅋㅋㅋㅋ 그냥 못 푼 풀이 def solution(N, stages): count_sort = [0] * (N+1) for i in range(0, stages): stages[0] tmp = sorted(stages) for i in range(1, N+1): answer = [] return answer 1-1. 풀이 도중 생각 1) 실패율 = (해당 스테이지에 머물러 있는 사람) / (해당 스테이지에 있는 사람 + 그 이상에 있는 사람) 2) 스테이지를 인덱스로 가지는 계수 정렬이 필요하려나? 3) 낮은 순으로 정렬한 다음에 분수 계산 하면 될 것 같은데 그걸 어떻게 해야는지 감이 안 잡히네 2. 정답 Hr.... count()라는 함수가 있는지 알았.. 2023. 2. 12. [이코테] 정렬 - 안테나 ㅋㅋㅋㅋㅋㅋ 정답 보니까 진짜 허무해지는 문제... 1. 내 풀이 n = int(input()) data = list(map(int, input().split())) distance = {} for i in range(n): tmp = 0 for j in range(0, n, -1): if j == 0: tmp += abs(data[i] - data[j]) distance[tmp] = i else: tmp += abs(data[i]-data[j]) keys = list(distance.keys()) keys.sort() print(distance[keys[0]]) 1-1. 풀이 도중 생각 1) 계수 정렬로 하기에는 공백이 너무 많이 생길 것 같은데? 2) 거리를 다 구해서 각 집 위치를 키를 가지는 딕셔.. 2023. 2. 12. 이전 1 2 3 4 5 6 다음