Algorithm/Dynamic Programming69 [파이썬] 백준 2253 : 점프 (골드4) [파이썬] 백준 2253 : 점프 (골드4) 2253번: 점프 N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 www.acmicpc.net 문제 풀이 0. 방향성 생각 전형적인 2차원 DP 같은 노드 x라도 어떤 속도로 접근했냐에 따라서 다음의 선택지가 바뀌므로 위치 x와 속도 v로 DP 테이블을 만든다 x번째 발판에 속도 v로 도달했을 때 최솟값을 DP에 기록하자. N = 10000이므로 최대 속도는 약 141이다. cf) 1+2+...+k = {k*(k-1)}/2 > N인 k를 찾는다. sqrt(20000) 넉넉잡아서 최대 속도를 1.. 2024. 2. 7. [파이썬] 백준 10217 : KCM Travel (플레5) [파이썬] 백준 10217 : KCM Travel (플레5) 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 www.acmicpc.net 문제 풀이 방향성 생각 다익스트라 + 2차원 visit (노드, 사용금액) = 시간기록 node가 100 / 지원비용 10000 = 100만이라서 메모리가 좀 빡빡해보인다 -> 당연하게도(?) 터져버림 최대로 지원금이 m으로 정해짐 -> 냅색? (사실 DP 태그보고 알았음 ㅋㅋ) 전체코드 import sys input = lambda : sys.stdin.readl.. 2023. 12. 25. [파이썬] 백준 1102 : 발전소 (플레5) [파이썬] 백준 1102 : 발전소 (플레5) 1102번: 발전소 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 www.acmicpc.net 문제 풀이 0. 방향성 생각 dfs로 순회해주면서 가지치기 / 메모제이션으로 시간 단축하기. 개수가 다 채워졌으면 다른 발전소를 키지 않는거는 자명한 사실이니까, 개수 체크해주기. 1. 입력 import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(10**6) def cvt(state): on = 0 string = '' for .. 2023. 12. 22. [파이썬] 백준 5624 : 좋은 수 (골드 3) [파이썬] 백준 5624 : 좋은 수 (골드 3) 5624번: 좋은 수 정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다) 수열이 주어졌을 때 www.acmicpc.net 문제 풀이 방향성 생각 입력이 5000이라 N^2까지 가능 처음 풀이는 순회 하면서 모든 조합을 저장해서 조회하는 식으로 했는데 시간 초과 현재 숫자 a에서 이전에 arr에서 등장했던 숫자 o를 빼면 a-o가 나온다. 이 a-o가 이전에 두 숫자의 조합으로 만들 수 있으면 그 숫자을 카운팅 경우의 수가 아니라, 각 위치에 있는 숫자가 좋은 수인지만 판별하면 된다. 전체코드 n = int(input()) .. 2023. 12. 18. 이전 1 ··· 6 7 8 9 10 11 12 ··· 18 다음
