BOJ 풀이 노트: 증가 부분수열 합 DP와 나이트 이동 BFS 점검

2026. 3. 2. · boj-note

오늘은 DP와 그래프 탐색을 하나씩 묶어서 2문제를 풀었다.

• BOJ 11055 - 가장 큰 증가하는 부분 수열
• BOJ 7562 - 나이트의 이동

11055는 “길이”가 아니라 “합”을 최대화하는 점이 핵심이고, 7562는 가중치 없는 격자 최단거리라 BFS를 정확히 구현하면 안정적으로 풀린다.

1) BOJ 11055 - 가장 큰 증가 부분 수열

문제 핵심 요약

수열에서 증가하는 부분수열을 골랐을 때, 그 원소들의 합이 최대가 되는 값을 구하는 문제다.

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

LIS(최장 증가 부분수열)와 비슷하지만 목적 함수가 길이가 아니라 합이다.

dp[i]를 “i번 원소를 마지막으로 사용하는 증가 부분수열의 최대 합”으로 두면,

• 초기값: dp[i] = a[i] (자기 자신만 선택)
• 전이: a[j] < a[i]인 모든 j < i에 대해 dp[i] = max(dp[i], dp[j] + a[i])

이렇게 하면 각 위치를 끝점으로 하는 최적해를 구할 수 있고, 전체 정답은 max(dp[i])가 된다.

시간/공간 복잡도

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

실수하기 쉬운 포인트

• LIS 문제 습관으로 +1을 하거나 길이 기준으로 구현하는 실수
• dp[i] 초기값을 0으로 두면 음수/작은 케이스에서 잘못될 수 있음 (이 문제는 자연수 수열이지만 패턴상 a[i] 초기화가 정석)
• 최종 정답을 dp[n-1]로 착각하는 실수 (항상 max(dp))

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

dp[i] = a[i];
for (int j = 0; j < i; ++j) {
    if (a[j] < a[i]) {
        dp[i] = max(dp[i], dp[j] + a[i]);
    }
}

“i에서 끝나는 최대 합”을 채우는 핵심 전이다.

answer = max(answer, dp[i]);

각 i마다 전역 최댓값을 갱신해 최종 정답을 만든다.

다른 풀이 가능성

• 좌표압축 + 펜윅트리(또는 세그먼트트리)로 “값 기준 최대 DP”를 관리하면 O(N log N)으로 개선 가능하다.
• 다만 입력 크기 기준으로는 O(N^2) DP가 구현/검증 측면에서 가장 실용적이다.

2) BOJ 7562 - 나이트의 이동

문제 핵심 요약

체스판 크기 L x L에서 나이트가 시작점에서 목표점까지 이동할 때 필요한 최소 이동 횟수를 구하는 문제다.

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

각 칸을 정점으로 보고, 나이트의 8가지 이동을 간선으로 보면 가중치 없는 그래프 최단거리 문제가 된다. 따라서 BFS가 정답이다. BFS는 먼저 도달한 거리가 항상 최소 거리다.

테스트케이스마다 거리 배열을 -1로 초기화하고 시작점을 0으로 두어 탐색했다.

시간/공간 복잡도

• 시간: 테스트케이스당 O(L^2)
• 공간: O(L^2)

실수하기 쉬운 포인트

• x/y 축 혼동으로 인덱스 뒤바뀜
• 범위 체크(0 <= nx, ny < L) 누락
• 방문 체크를 늦게 해서 큐에 같은 좌표가 여러 번 들어가는 문제
• 시작점과 도착점이 같은 경우(정답 0) 처리 누락

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

dist[sx][sy] = 0;
q.push({sx, sy});

BFS 시작 상태를 잡는 부분. dist == -1을 미방문으로 사용한다.

if (nx < 0 || nx >= l || ny < 0 || ny >= l) continue;
if (dist[nx][ny] != -1) continue;
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});

경계/방문 검사를 통과한 칸만 확장해 최단거리 성질을 보장한다.

다른 풀이 가능성

• 양방향 BFS를 적용해 평균 탐색 범위를 줄일 수 있다.
• 하지만 일반 BFS만으로도 충분히 통과 가능하고 구현 안정성이 높다.

오늘 정리 포인트는 두 가지다.

• DP는 “무엇을 최적화하는지(길이 vs 합)“에 따라 상태 정의가 달라진다.
• 그래프 최단거리는 가중치가 없으면 BFS가 기본 해법이다.

기본기를 이런 식으로 매일 2문제씩 고정 루틴으로 반복하면, 구현 실수 빈도와 풀이 시간이 눈에 띄게 줄어든다.