BOJ 1214 : 쿨한 물건 구매
문제 링크 : https://www.acmicpc.net/problem/1214사전 지식 / 관련 알고리즘 : 수학 Pa + Qb ≥ D 가 되어야 한다.가장 먼저 드는 생각은, P 의 개수 a 를 0, 1, 2, ... 로 늘려가면서, 그에 맞는 b 의 최솟값을 찾는 것이다. P의 개수 a 가 결정된다면, Qb ≥ D - Pa 이고, 이를 만족하는 자연수 b 의 최솟값은 ⌈ (D-Pa) / Q ⌉ 이다.이를 깔끔하게 구하는 법은, 분자에 Q-1 을 더하고 나누는 것이다.즉, ⌈ (D-Pa) / Q ⌉ 는 ceil 함수 없이 (D-Pa+Q-1) / Q 로 구할 수 있다. 하지만, 이러면 시간 초과가 날 수 있다.만약 D = 10억, P = 2 라면,a 의 범위는 0, 1, 2, ... 5억 까지도 가능하..
2025. 5. 23.
BOJ 1126 : 같은 탑
문제 링크 : https://www.acmicpc.net/problem/1126사전 지식 / 관련 알고리즘 : 다이나믹 프로그래밍 (DP) 처음 이 문제를 접했을 때, 며칠 동안 시간이 나는 대로 조금씩 고민했었는데, 결국 풀어냈을 때 매우 짜릿했다.DP 의 정의를 떠올리는 관찰이 어렵지, 그 후 점화식을 세우는 것과 코딩을 하는 것 모두 쉽다. DP 의 상태로 가능한 변수들에는 어떤 것들이 있을까? 대부분의 DP 문제들이 그렇듯,조각이 1개 있을 때, 2개 있을 때, 3개 있을 때, ..., N개 있을 때 즉, 우리가 현재 "고려하고 있는 조각의 개수"를 x 로 두자.ex) x = 5 라는 것은, 1번 ~ 5번 조각까지만 고려한다는 것이다. 5번 조각을 반드시 쓸 필요는 없다. 우리의 목표는 두 탑의..
2025. 5. 23.
