seukseok의 개인 블로그

BOJ 풀이 노트: 역추적 그리디와 조합 백트래킹 점검

· tech

오늘은 16953과 1759를 묶어, 정방향 BFS 대신 역방향 축소로 푸는 아이디어와 사전순 조합 생성에서 조건 검증을 분리하는 구현 포인트를 정리했다.

오늘은 연산 변환 1문제 + 조합 생성 1문제로 루틴을 구성했다.

하나는 “앞에서 만들지 말고 뒤에서 줄여보는” 관점 전환이 핵심이고, 다른 하나는 백트래킹 기본기를 깔끔하게 점검하기 좋은 문제다.

1) BOJ 16953 - A → B

문제 핵심 요약

정수 A를 시작으로 2를 곱하기, 1을 오른쪽에 붙이기 두 연산만 사용해서 B를 만들 때, 필요한 최소 연산 횟수를 구하는 문제다. 불가능하면 -1을 출력한다.

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

정방향으로 A -> B를 탐색하면 분기가 생겨 탐색량이 커질 수 있다. 이 문제는 연산의 역연산이 매우 단순해서, B에서 시작해 A로 줄여 가는 방식이 더 직관적이고 빠르다.

각 단계에서 가능한 선택이 사실상 강제되므로, 별도 BFS 없이 그리디하게 진행해도 정답을 얻을 수 있다.

시간/공간 복잡도

실수하기 쉬운 포인트

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

while (B > A) {
    if (B % 10 == 1) {
        B /= 10;
        ++steps;
    } else if (B % 2 == 0) {
        B /= 2;
        ++steps;
    } else {
        break;
    }
}

역방향으로 줄일 수 있는 경우만 처리하고, 불가능한 패턴이 나오면 즉시 종료한다.

if (B == A) cout << steps << '\n';
else cout << -1 << '\n';

루프 이후 도달 여부를 명확히 분기해서 정답/실패를 출력한다.

다른 풀이 가능성

2) BOJ 1759 - 암호 만들기

문제 핵심 요약

주어진 문자 C개 중 L개를 골라 암호를 만든다. 암호는 사전순이어야 하고, 최소 1개의 모음과 최소 2개의 자음을 포함해야 한다. 가능한 모든 암호를 사전순으로 출력한다.

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

핵심은 “사전순 조합 생성”이다. 입력 문자를 먼저 정렬한 뒤, 인덱스 증가 방향으로 L개를 뽑는 조합 DFS를 돌리면 출력 자체가 사전순으로 보장된다.

조건(모음/자음 개수)은 조합을 완성했을 때 한 번만 검증해도 충분하다. 이렇게 하면 생성 로직과 검증 로직이 분리되어 디버깅이 쉬워진다.

시간/공간 복잡도

실수하기 쉬운 포인트

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

sort(chars.begin(), chars.end());

사전순 출력을 보장하기 위한 전처리다.

for (int i = idx; i < C; ++i) {
    picked.push_back(chars[i]);
    dfs(i + 1, cnt + 1);
    picked.pop_back();
}

다음 선택 시작점을 i + 1로 넘겨 조합만 생성한다.

if (vowels >= 1 && consonants >= 2) {
    for (char c : picked) cout << c;
    cout << '\n';
}

완성된 후보에 대해 문제 조건을 최종 검증한다.

다른 풀이 가능성

오늘 정리 포인트: