Algorithm/Dynamic Programming69 [파이썬] 백준 1660 : 캡틴 이다솜 (골드5) [파이썬] 백준 1660 : 캡틴 이다솜 (골드5)https://www.acmicpc.net/problem/1660풀이방향성 생각사면체 만드는데 필요한 블럭 단위를 미리 만들어놓는다i개를 사용해서 만들 때, 블럭단위에 있는 t개 + dp[i-t]가 최소값인 경우 갱신전체코드N = int(input())dp = [1e9]*(N+1)tetra = [(n*(n+1)*(n+2))//6 for n in range(1,121) if (n*(n+1)*(n+2))//6 t: dp[i] = min(dp[i],dp[i-t]+1) else: breakprint(dp[N])코멘트python으로 잘 안돌아감$O(100N)$이라 안터질줄 알았는데 터져서 pypy로 풀이 2024. 11. 15. [파이썬] 백준 1633 : 최고의 팀 만들기 (골드4) [파이썬] 백준 1633 : 최고의 팀 만들기 (골드4)https://www.acmicpc.net/problem/1633풀이방향성 생각state가 어떻게 결정되는지 생각한다.N>30인 경우에는 안뽑히는 사람도 존재한다.k명을 뽑았을 때, 흑팀의 수 b, 백팀의 수 w로 상태가 나뉜다.접근은 remain black, remain white, choose k로 시작했다.DFS를 통해서 뽑아야 하는 B와 W의 숫자,현재 탐색중인 사람 idx를 넘겨줬다.전체코드from collections import defaultdict as ddarr = []while True: try: arr.append(tuple(map(int,input().split()))) except: brea.. 2024. 10. 1. [파이썬] 백준 10942 : 팰린드롬? (골드4) [파이썬] 백준 10942 : 팰린드롬? (골드4)https://www.acmicpc.net/problem/10942풀이방향성 생각전형적인 DP각 쿼리마다 체크하거나, $N^2$로 체크하면 시간초과한다.시간 제한이 0.5초이고 쿼리 개수가 많아서 DP 리스트에 접근하면 시간초과.DP를 통해서 순회를 줄인 후, 쿼리를 결과를 출력한다.전체코드import sysinput = lambda : sys.stdin.readline().rstrip()N = int(input())arr = list(map(int,input().split()))dp = [[0]*(N) for _ in range(N)] #dp[시작idx][끝idx]# 길이 1은 팰린드롬for i in range(N): dp[i][i] = 1# 길이.. 2024. 8. 4. [파이썬] 백준 9465 : 스티커 (실버1) [파이썬] 백준 9465 : 스티커 (실버1)https://www.acmicpc.net/problem/9465풀이방향성 생각상태를 나누는 기준은 줄 선택 / 이전에 스티커를 선택했는지 -> 2*2로 총 4가지이다.이전에 스티커를 선택한 경우 : 스티커를 선택하지 않은 경우 2가지 + 스티커를 선택한 경우 (반대 줄에서)이전에 스티커를 선택하지 않은 경우 : 스티커를 선택하지 않은 경우 2가지 + 스티커를 선택한 경우 2가지전체코드import sysinput = lambda : sys.stdin.readline().rstrip()def dp(N,arr): V = [[[0]*N for _ in range(2)] for _ in range(2)] V[1][1][0] = arr[1][0] V[1.. 2024. 8. 1. 이전 1 2 3 4 5 6 7 8 ··· 18 다음