[BaekJoon 14626][🟤1] ISBN

❓ 문제

백준 14626 - “ISBN”

🎯 난이도

Bronze 🟤1

🧠 풀이

1. 내 풀이 (브루트 포스)

- 알고리즘

• Brute Force, Mathematics

- 설명

브루트 포스 알고리즘을 사용한 풀이이다.

문자열을 순회하며 각 숫자와 가중치를 곱해주며 전체 합을 구하고, *의 자리를 알아내어 가중치를 구하고, 0 <= N < 10 구간을 브루트 포스로 루프를 돌며 답을 찾아내는 방식이다.

가장 직관적이고 실수가 나올 부분이 적기 때문에 정석적인 풀이라고 볼 수 있다.

루프를 한 번 돌며 계산하므로 시간 복잡도는 O(N)이지만, N = 13이기에 거의 상수에 가깝다

- 코드

내 풀이 코드

#include <iostream>

#include <string>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string strInput{};
    cin >> strInput;

    int iSum{}; // *를 제외한 모든 합
    int iWeight{};  // *의 가중치
    for(int i = 0; i < static_cast<int>(strInput.length()); ++i)
    {
        if(strInput[i] == '*')
        {
            iWeight = i % 2 == 0 ? 1 : 3;
            continue;
        }

        iSum += (strInput[i] - '0') * (i % 2 == 0 ? 1 : 3);
    }

    // 0 ~ 9를 순회하며 *의 값을 찾는다
    for(int i = 0; i < 10; ++i)
    {
        if((iSum + i * iWeight) % 10 == 0)
        {
            cout << i;
            return 0;
        }
    }

    return 0;
}

---

2. 추가 풀이 (수학적 풀이)

- 알고리즘

• Mathematics, Arithmetic

- 설명

나머지 연산의 특성을 사용한 수학적 풀이이다.

이 문제를 수식화하면 다음과 같다.

\[(Sum + Weight * X) \% 10 == 0\]

여기서 Weight이 1일 때와 3일 때가 갈린다.

• Weight == 1인 경우

\[X = (10 - Sum \% 10) \% 10\]

• Weight == 3인 경우 (3의 역원은 7)

\[3X ≡ -Sum (mod 10)\] \[X = 7 * (10 - Sum \% 10) (mod 10)\]

따라서 Sum을 구해주고 분기별로 따로 결과값을 계산만 하면, '브루트 포스'처럼 루프를 돌지 않고도 한 번에 결과값을 도출할 수 있다.

하지만 이러한 방법은 이론상 빠르긴 하지만, 수식을 이끌어내는 과정에서 실수가 있을 수 있고, 직관성도 좋지 않다. 그래도 알아두면 좋을 것 같은 풀이이다.

Sum을 구하는 방식은 O(N)이지만 결과 도출이 O(1)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <string>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string strInput{};
    cin >> strInput;

    int iSum{}; // *를 제외한 모든 합
    int iWeight{};  // *의 가중치
    for(int i = 0; i < static_cast<int>(strInput.length()); ++i)
    {
        if(strInput[i] == '*')
        {
            iWeight = i % 2 == 0 ? 1 : 3;
            continue;
        }

        iSum += (strInput[i] - '0') * (i % 2 == 0 ? 1 : 3);
    }

    int iResult{};
    int iRight{ (10 - iSum % 10) % 10 };    // 식에 따라 우변에 들어갈 값

    if(iWeight == 1)
    {
        iResult = iRight;
    }
    else
    {
        // iWeight == 3인 경우 역원인 7을 곱해주어야 함
        iResult = (7 * iRight) % 10;
    }

    cout << iResult;

    return 0;
}

---

💭 후기

브루트 포스로 쉽게 풀 수 있는 문제를 나머지 연산의 특성을 사용해서 수식화하여 더 효율적인 풀이로 만들 수 있는 문제이다.

나머지 연산의 정확한 원리를 알아두면 앞으로 문제 풀 때 많은 도움이 될 것 같다.

🔗 참고자료

• 브루트 포스 알고리즘