코딩테스트/다이나믹 프로그래밍3 [백준] 2839번 설탕배달(파이썬) 문제 이 문제는 DP(동적 계획법)로 해결하는 전략을 선택했다.처음에는 5가 가장 큰 단위이므로 5로 나누어 떨어지는지 확인한 뒤, 그렇지 않을 경우를 중심으로 접근하면 어떨까 생각했다. 하지만 이러한 방식으로 접근하면 쉽게 막힐 수 있다.핵심 1. 작은 경우부터 차근차근 해결해 나가면서 비교하는 것이 중요하다.2. 이전에 계산된 3과 5의 경우의 수를 조합하여 최적의 값을 찾아가는 방식으로 접근해야 한다. 내가 했던 풀이 n=int(input())dp=[-1]*(n+1)if n 초기에 바로 판별할 수 있는 경우들은 즉시 정답을 출력하도록 처리했다.이후, 문제를 다음 세 가지 경우로 나누어 해결했다.5로 나누어 떨어지는 경우3으로 나누어 떨어지는 경우어느 쪽으로도 나누어지지 않는 경우그다음,5로 나누.. 2025. 3. 2. [백준] 1309번 동물원 (파이썬) 문제 설명https://www.acmicpc.net/problem/1309이 문제는간단히 설명하자면 2*n일 때 사자를 어떻게 배치할 수 있을지 파악하는 문제이다.사자의 갯수는 한정적이지 않고 n에 수에 따라 바뀐다.핵심2*n 크기의 우리에 따라 사자의 배치 가능한 경우의 수가 달라진다. 이를 해결하기 위해 먼저 점화식을 세우는 것이 중요했고, 이를 위해 직접 여러 경우를 계산해보았다.가로축은 사자의 수를, 세로축은 n에 따른 배치 가능한 경우의 수를 나타낸 그래프이다.사자의 수를 기준으로 우리의 크기 n의 변화에 따른 규칙을 분석했다.사자가 0마리일 때는 항상 1이고, 1마리일 때는 2×n, 2마리일 때는 2ⁿ만큼 증가하는 규칙을 발견했다.하지만 3마리 이상에서는 규칙을 찾을 수 없었다.따라서 다른 접.. 2025. 1. 26. [백준] 2565번 전깃줄 (파이썬) 문제 설명https://www.acmicpc.net/problem/2565참고 블로그: https://hongcoding.tistory.com/157코드n=int(input())elec_list=[]dp=[1]*nfor i in range(n): a,b=map(int,input().split()) elec_list.append([a,b])elec_list.sort()for i in range(1,n): for j in range(0,i): if elec_list[j][1]핵심이 문제는 어떤 상태가 크로스 했다는 것을 알아야 한다.내가 풀었던 실수처음에는 전선이 교차하는 상태를 코드로 어떻게 구현해야 할지 전혀 떠올리지 못했다.또한 교차된 전선을 삭제해야 하는데, 이를 코드로 .. 2025. 1. 26. 이전 1 다음
