[백준/C++] 25370번 카드 숫자 곱의 경우의 수

---

그냥 문제 하나 간단하게 풀고 싶어서 도전한 문제이다.

곱셈에 패턴이 보이지는 않고 1~9까지의 카드를 최대 7장 뽑는다면 매우 작은 숫자니 브루트포스 문제라고 생각하였다.

 

그러다 문득 곱셈이니 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1로 생각해보면

1~9를 곱한 것에 다시 1 ~ 9를 곱하는 형식을 N번 반복하는 형태가 되겠다는 생각을 하게 되었다.

set을 이용해 중복 없이 key를 사용하면 편하겠다 생각했는데 sort가 되는 문제가 있어 배열 2개를 사용하여 중복 체크를 한 후 배열에 값들을 담아내는 형식으로 구현했다. (최대숫자도 400만 언저리니 배열 크기를 널널하게 잡았다.)

---

/**
 * @file 25370.cpp
 * @author fpqpsxh
 * @date 2023-01-17
 **/
#include <bits/stdc++.h>
using namespace std ;
bool checker[5000000] ;
int N, answer ;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0) ;
    cin >> N ;
    vector<int> arr ;
    checker[1] = 1 ;
    arr.push_back(1) ;

    for(int i = 0 ; i < N ; i++)
    {
        int size = arr.size() ;
        for(int j = 0 ; j < size ; j++)
            for(int k = 1 ; k <= 9 ; k++)
            {
                int tmp = arr[j] * k ;
                if(!checker[tmp])
                {
                    checker[tmp] = 1 ;
                    arr.push_back(tmp) ;
                }
            }
    }

    cout << arr.size() ;
}

---

시간 0ms로 1페이지에 들어갔다!

---

느낀점: 뭔가 sort랑 unique erase를 사용해서 풀고 싶지 않아 이렇게 구현해보았는데 확실히 속도는 빠른 것 같다.

문제: https://www.acmicpc.net/problem/25370

25370번: 카드 숫자 곱의 경우의 수