(C++) - 백준(BOJ) 10372번 : Alarm Clock

https://www.acmicpc.net/problem/10372

10372번: Alarm Clock

brute force 문제였습니다.

 

 

📕 풀이방법

 

 1. 0은 그림을 확인해보시면 6개의 획입니다. 1은 5, 2는 5... 이런식으로 9까지 획을 모두 저장합니다.

 

 2. 10개의 digit 중 4개를 뽑습니다. 뽑아낸 숫자가 시간과 분을 나타내기 위한 조건에 맞다면 string 변수 ans에 저장합니다.

 

 3. ans가 하나라도 있다면 ans를 아니면 Impossible을 출력합니다.

---

 

 

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, ck[10], digit[10] = {6,2,5,5,4,5,6,3,7,6}; 
string ans;
vector <int> v;

void dfs(int depth){
    if(depth == 4) {
        int cnt = 0;
        for(int i = 0; i < v.size(); i++) cnt += digit[v[i]];
        string hour = to_string(v[0]) + to_string(v[1]);
        string minute = to_string(v[2]) + to_string(v[3]);
        if(cnt == n && hour < "24" && minute < "60") ans = hour + ":" + minute;
        return;
    }

    for(int i = 0; i < 10; i++){
        v.push_back(i);
        dfs(depth + 1);
        v.pop_back();
    }
}

int main(){
    cin >> n;
    dfs(0);
    if(ans.size()) cout << ans;
    else cout << "Impossible";
}