[C++] 백준/Gold/2011. 암호코드

2025. 3. 19. 21:43·C++/Algorithm

문제: 암호 코드 (백준 2011번)

문제 분석

  • 주어진 숫자 문자열을 알파벳으로 변환하는 경우의 수를 찾는 문제.
  • '1' ~ '26'까지의 숫자는 각각 'A' ~ 'Z'로 변환 가능.
  • '0'은 단독으로 존재할 수 없으며, 반드시 앞 숫자와 조합되어야 한다.

풀이: 동적 계획법 (DP)

1. DP 배열 정의

  • dp[i] = 주어진 숫자에서 i번째 숫자까지 해석할 수 있는 방법의 수
  • 핵심은 한 자리, 두 자리씩 해석하는 경우를 고려하는 것이다.

2. 점화식

  • 1자리 숫자로 해석 가능한 경우 (num[i-1] ≠ '0')
    • → dp[i] += dp[i-1]
  • 2자리 숫자로 해석 가능한 경우 (10 ≤ 두 자리 숫자 ≤ 26)
    • → dp[i] += dp[i-2]
  • MOD 연산 적용: dp[i] %= 1000000
    • 문제에서 요구하는 값이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 저장한다.

코드 설명

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    string num; cin >> num;

    if (num[0] == '0') // 첫 번째 자리가 0이면 해석 불가
    {
        cout << 0;
        return 0;
    }

    int n = num.size();
    vector<int> dp(n + 1);
    dp[0] = 1; // 아무것도 해석하지 않은 경우 (기본값)
    dp[1] = 1; // 첫 번째 숫자는 한 가지 방법으로 해석 가능

    for (int i = 2; i <= n; i++)
    {
        int oneDigit = num[i - 1] - '0';       // 현재 한 자리 숫자
        int twoDigit = stoi(num.substr(i - 2, 2)); // 현재 두 자리 숫자

        if (oneDigit > 0) // 1~9 범위일 때
            dp[i] = (dp[i] + dp[i - 1]) % 1000000;

        if (10 <= twoDigit && twoDigit <= 26) // 10~26 범위일 때
            dp[i] = (dp[i] + dp[i - 2]) % 1000000;
    }

    cout << dp[n];
}

'C++ > Algorithm' 카테고리의 다른 글

[C++] 백준/Platinum/1786. 찾기  (0) 2025.03.28
[C++] LeetCode/Hard/0745-prefix-and-suffix-search  (0) 2025.03.25
[C++] 백준/Gold/1915. 가장 큰 정사각형  (0) 2025.03.14
[C++] 백준/Gold/1253. 좋다  (0) 2025.03.13
[C++] 백준/Gold/2023. 신기한 소수  (0) 2025.03.12
'C++/Algorithm' 카테고리의 다른 글
  • [C++] 백준/Platinum/1786. 찾기
  • [C++] LeetCode/Hard/0745-prefix-and-suffix-search
  • [C++] 백준/Gold/1915. 가장 큰 정사각형
  • [C++] 백준/Gold/1253. 좋다
돼지표
돼지표
https://github.com/wkdgns135
  • 돼지표
    돼지표 개발 스토리
    돼지표
  • 전체
    오늘
    어제
    • 분류 전체보기 (99)
      • C++ (58)
        • Algorithm (52)
      • Python (1)
      • Machine Learning (2)
      • Computer Graphics (4)
        • Curly Hair Simulation (2)
      • GPU Programming (11)
        • CUDA basic (7)
        • CUDA fluidsGL (4)
      • Unreal 5 (20)
        • Troubleshooting (4)
        • FPS Shooting (5)
        • Study (9)
        • EOS (1)
      • Computer Science (3)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • Github
  • 공지사항

  • 인기 글

  • 태그

    CUDA
    그리디 알고리즘
    C++
    Fluid Simulation
    Algorithm
    수학
    dp
    CS
    아이작 맵 생성
    unreal 5
    FPS
    Rendering Pipeline
    구현
    BFS
    OpenGL
    위상 정렬
    UE5
    GPU Programming
    자료 구조
    그래프 탐색
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
돼지표
[C++] 백준/Gold/2011. 암호코드
상단으로

티스토리툴바