BOJ 풀이 노트: DP와 BFS 기본기 점검

2026. 2. 22. · tech

BOJ 14501, 1697을 문제 핵심, 접근 이유, 복잡도, 실수 포인트, 핵심 코드 라인과 대안 풀이 관점으로 정리한 실전 노트.

오늘은 유형이 다른 두 문제를 묶어서 풀었다.

• BOJ 14501 - 퇴사
• BOJ 1697 - 숨바꼭질

하나는 일정 선택형 DP, 다른 하나는 최단 시간 탐색 BFS다. 둘 다 코딩 테스트에서 자주 재등장하는 기본 패턴이라 루틴 점검용으로 좋았다.

1) BOJ 14501 - 퇴사

문제 핵심 요약

N일 동안 상담 일정이 주어지고, 각 상담은 소요 일수 T[i]와 수익 P[i]를 가진다. 퇴사일(N+1일) 전까지 상담을 겹치지 않게 선택해 최대 수익을 구하는 문제다.

접근 아이디어(왜 이 방법인지)

매일 “오늘 상담을 한다 / 안 한다” 선택이 생기고, 오늘의 선택이 미래 가능한 상태를 바꾼다. 이 구조는 전형적인 DP다.

• dp[d]: d일이 끝났을 때 얻을 수 있는 최대 수익
• 오늘 상담을 안 하면 dp[day + 1]로 수익 이월
• 오늘 상담을 하면 day + T[day] 시점으로 점프하며 수익 추가

이 방식이면 겹침 처리와 퇴사일 초과 검사를 자연스럽게 함께 처리할 수 있다.

시간/공간 복잡도

• 시간: O(N)
• 공간: O(N)

실수하기 쉬운 포인트

• 상담 종료일 검사를 day + T[day] <= N + 1로 해야 한다. (N이 아니라 N+1 기준)
• “오늘 안 하는 경우” 이월(dp[day+1] = max(dp[day+1], dp[day]))을 빼먹으면 정답이 줄어든다.
• 인덱스를 0-based/1-based 섞으면 경계에서 오답이 잘 난다.

C++ 코드 설명(핵심 라인)

dp[day + 1] = max(dp[day + 1], dp[day]);

• 상담을 건너뛰는 선택을 반영해 다음 날 상태를 유지한다.

int endDay = day + T[day];
if (endDay <= N + 1) {
    dp[endDay] = max(dp[endDay], dp[day] + P[day]);
}

• 오늘 상담을 선택할 수 있을 때만 종료 시점 상태를 갱신한다.

다른 풀이 가능성

뒤에서 앞으로 가는 역방향 DP(dp[i] = max(dp[i+1], P[i] + dp[i+T[i]]))도 가능하다. 핵심은 동일하게 “상담 선택 vs 스킵” 비교다.

2) BOJ 1697 - 숨바꼭질

문제 핵심 요약

수빈이의 위치 N에서 동생 위치 K까지 가는 최소 시간을 구한다. 한 번에 할 수 있는 이동은 x-1, x+1, 2*x다.

접근 아이디어(왜 이 방법인지)

모든 이동 비용이 1초로 동일하므로, 최단 시간은 BFS로 구하는 것이 정석이다.

• 정점: 위치(0~100000)
• 간선: 세 가지 이동
• BFS로 처음 도달한 시간이 해당 위치의 최소 시간

가중치가 모두 같다는 점이 다익스트라보다 BFS를 쓰는 이유다.

시간/공간 복잡도

• 시간: O(MAX) (MAX=100000 범위 내 각 위치를 최대 1회 방문)
• 공간: O(MAX)

실수하기 쉬운 포인트

• 방문 범위를 벗어나는 인덱스(-1, 100001) 처리 누락
• 방문 체크 없이 큐에 계속 넣어 중복 탐색이 커지는 문제
• 위치가 아니라 “시간” 기준으로 헷갈려 dist 배열 초기화를 잘못하는 경우

C++ 코드 설명(핵심 라인)

vector<int> dist(MAX + 1, -1);
dist[N] = 0;
q.push(N);

• -1을 미방문 표식으로 두고 시작점을 0초로 초기화한다.

int nextPos[3] = {cur - 1, cur + 1, cur * 2};
for (int nx : nextPos) {
    if (nx < 0 || nx > MAX) continue;
    if (dist[nx] != -1) continue;
    dist[nx] = dist[cur] + 1;
    q.push(nx);
}

• 경계 검사 + 미방문 검사 후 다음 상태를 큐에 넣는다. BFS 레벨 특성상 최초 도달이 최단 시간이다.

다른 풀이 가능성

양방향 BFS를 적용해 탐색 폭을 줄일 수는 있지만, 이 문제 범위에서는 일반 BFS만으로도 충분히 통과 가능하고 구현 실수도 적다.

오늘 정리 포인트:

• 14501은 상태 정의(dp[d])를 명확히 잡으면 코드가 짧고 안전해진다.
• 1697은 “동일 가중치 최단 거리 = BFS” 공식을 바로 적용하는 판단 속도가 중요하다.

전형 문제를 꾸준히 정리해두면, 실전에서 풀이 선택 자체가 빨라진다.