코후닝

Yonsei Formula 1 백준 DP, 이분 탐색 ⏱️ 읽기 시간: 약 7분 📑 목차 1. 문제 분석 2. 접근법 3. 풀이 (Java) 4. 예제 트레이스 5. 복잡도 분석 6. 클린 코드 문제 분석 둘레 L인 원형 트랙을 M바퀴 완주해야 한다. N개의 타이어가 주어지고, 순서대로만 교체 가능하다 (건너뛰기는 가능). 타이어 교체는 시작 지점(위치 0)에서만 가능하며, 교체 시간은 0이다. 타이어 i의 성능: 초기 ai에서 시작해 매 분 di씩 감소, bi에 도달하면 더 이상 감소하지 않는다. 매 분 [0, v..

등차수열 백준 1994 Gold III DP · 정렬 문제 분석 N개의 음이 아닌 정수 중 일부를 골라 나열했을 때, 만들 수 있는 가장 긴 등차수열의 길이를 구하는 문제 등차수열의 공차는 양수, 0, 음수 모두 가능 원소를 자유롭게 나열할 수 있으므로, 정렬 후 가장 긴 등차 부분수열(LAS)을 찾으면 된다 제약: N ≤ 2,000 / 값 ≤ 109 접근법 DP on sorted pairs — O(N²) 정렬된 배열에서 dp[i][j]를 "인덱스 i, j를 마지막 두 원소로 하는 등차수열의 최대 길이"로 정의한다. 공차 d = a[j] - a[i]이면, ..