새로운 불면증 치료법 C++(SW Expert Academy)

난이도 : D2

문제번호 : 1288

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18_yw6I9MCFAZN&categoryId=AV18_yw6I9MCFAZN&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

민석이는 불면증에 걸렸다. 그래서 잠이 안 올 때의 민간요법 중 하나인 양 세기를 하려고 한다. 민석이는 1번 양부터 순서대로 세는 것이 재미없을 것 같아서 N의 배수 번호인 양을 세기로 하였다. 즉, 첫 번째에는 N번 양을 세고, 두 번째에는 2N번 양, … , k번째에는 kN번 양을 센다. 이렇게 숫자를 세던 민석이에게 잠은 더 오지 않고 다음과 같은 궁금증이 생겼다. 이전에 셌던 번호들의 각 자리수에서 0에서 9까지의 모든 숫자를 보는 것은 최소 몇 번 양을 센 시점일까? 예를 들어 N = 1295이라고 하자. 첫 번째로 N = 1295번 양을 센다. 현재 본 숫자는 1, 2, 5, 9이다. 두 번째로 2N = 2590번 양을 센다. 현재 본 숫자는 0, 2, 5, 9이다. 현재까지 본 숫자는 0, 1, 2, 5, 9이다. 세 번째로 3N = 3885번 양을 센다. 현재 본 숫자는 3, 5, 8이다. 현재까지 본 숫자는 0, 1, 2, 3, 5, 8, 9이다. 네 번째로 4N = 5180번 양을 센다. 현재 본 숫자는 0, 1, 5, 8이다. 현재까지 본 숫자는 0, 1, 2, 3, 5, 8, 9이다. 다섯 번째로 5N = 6475번 양을 센다. 현재 본 숫자는 4, 5, 6, 7이다. 현재까지 본 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9이다. 5N번 양을 세면 0에서 9까지 모든 숫자를 보게 되므로 민석이는 양 세기를 멈춘다.

제약사항

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

입력

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고, 두 번째 줄에는 Ai, 세 번째 줄에는 Bj 가 주어진다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최소 몇 번 양을 세었을 때 이전에 봤던 숫자들의 자릿수에서 0에서 9까지의 모든 숫자를 보게 되는지 출력한다. ( 민석이는 xN번 양을 세고 있다. )

예시

입력	출력
5 1 2 11 1295 1692	#1 10 #2 90 #3 110 #4 6475 #5 5076

---

2. 문제풀이

입력값 N을 k배 했을때 나온 자리수가 0~9까지 모두되었을때를 출력하는 것입니다. 그렇다면 N을 자리수별로 분리하여 나온수를 체크하고 0~9까지 모두 나왔을때 멈추면 됩니다. 자리수 분리는 나머지 연산(%)와 몫 연산(/)을 이용해서 계산했습니다.   블로그 쓰면서 생각한건데 마지막에 0~9까지 나온것을 체크할때는 해쉬를 이용하여 해쉬의 길이가 10이라면 멈추게 하는게 좀더 효율적일거 같습니다.

 

---

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//1288 D2 새로운 불면증 치료법
int main() {
    //전체 반복횟수 입력받고 반복
    int len;
    cin >> len;
    for (int l = 1; l <= len; l++) {
        //n과 반복횟수를 나타내는 i, 숫자체크용 a
        int n, i = 1;
        vector<int> a(10, 1);
        cin >> n;
        bool check = false;
        //0~9까지 모든수가 나올때까지 반복
        for (i = 1; ; i++) {
            int temp = i * n;
            //한번도 걸리지 않았다면 반복문 탈출
            if (check)    break;
            check = true;
            //수를 쪼개면서 체크하기
            while (temp) {
                if (a[temp % 10])    a[temp % 10] = 0;
                temp /= 10;
            }
            //0번부터 9번까지 돌면서 모든값이 있나 체크하기
            for (int j = 0; j < 10; j++) {
                if (a[j]) {
                    check = false;
                    continue;
                }
            }
        }
        //값 출력하기
        cout << "#" << l << " " << (i-1)*n << endl;
    }
    return 0;
}