[Week14] 철수의 7 세그먼트 숫자놀이

#include <iostream> #include <fstream> #include <vector> #include <algorithm> #include <functional> #include <string> using namespace std; int number_count; string number; vector<vector<pair<int, int>>> big; int DP(int rest, int index) { if (number_count <= index) return 0; for (int j = 0; j < 7; j++) { int temp = rest - big[number[index] - '0'][j].second; if (big[number[index] - '0'][j].first == -1) return 0; if (temp < 0) continue; if (temp == 0) { number[index] = big[number[index] - '0'][j].first+'0'; return 1; } if (DP(temp, index + 1) == 1) { number[index] = big[number[index] - '0'][j].first + '0'; return 1; } } } int main() { ifstream fcin; fcin.open("C_small_input.txt"); ofstream fcout; fcout.open("C_small_answer.txt"); // 차이, 숫자 (숫자에서 n차이가 나는 수 중에 가장 큰 숫자) int example[100] = { 0,8,9,7,4,-1,-1,1,7,4,3,9,8,6,2,-1,8,9,7,4,-1,3,9,8,6,-1,-1,-1,4,-1,9,8,6,2,-1,5,9,8,4,7,1,-1,6,8,9,3,4,7,1,7,1,3,9,8,6,-1,8,9,5,4,7,1,-1,9,8,6,7,1,-1,-1 }; big = vector<vector<pair<int, int>>>(10); int ex_index = 0; for (int j = 0; j < 10; j++) { for (int k = 0; k < 7; k++) big[j].push_back(make_pair(example[ex_index++], k)); sort(big[j].begin(), big[j].end(), greater<pair<int, int>>()); } int for_count, difference; fcin >> for_count; while (for_count--) { fcin >> number_count >> number >> difference; DP(difference, 0); for (int j = 0; j < number_count; j++) fcout << number[j] - '0'; fcout << endl; } system("pause"); }

각 세그먼트에 순서대로 index를 붙여두고(차이를 확인하기 위하여) 정해두고 숫자A -> 숫자 B가 되려면 얼마나 차이가 있는지 미리 구해두었다

+) 그 때 사용했던 코드

#include <iostream> #include <vector> #include <string> #include <fstream> #include <algorithm> using namespace std; vector<vector<string>> number; int main() { ofstream fcout; fcout.open("C_difference.txt"); number = vector<vector<string>>(10, vector<string>()); number[0].push_back("1110111");//0 number[1].push_back("0010010");//1 number[2].push_back("1011101");//2 number[3].push_back("1011011");//3 number[4].push_back("0111010");//4 number[5].push_back("1101011");//5 number[6].push_back("1101111");//6 number[7].push_back("1010010");//7 number[8].push_back("1111111");//8 number[9].push_back("1111011");//9 for (int j = 0; j < 10; j++) { vector<int>temp = vector<int>(9, -1); for (int k = 0; k < 10; k++) { int count = 0,index=0; for (int p = 0; p < 7; p++) { if (number[j][0][p] != number[k][0][p]) count++; } temp[count] = max(temp[count], k); } for (int j = 0; j < 7; j++) fcout << temp[j] << " "; fcout << endl; } vector<vector<string>>cache = vector<vector<string>>(10, vector<string>(10)); cache[1][1].push_back(1+'0'); cache[1][1].push_back(2+'0'); cout << cache[1][1] << endl; system("pause"); }

이후 그 숫자들의 큰 순서대로 정렬하였다.

DP함수를 사용하였는데

차이는 최대 7까지 나기 때문에 j는 7로 두었다.

이후 

현재의 값이 -1이면 그 전으로 바로 넘어가고

나머지가 0이하이면 continue

나머지가 0이면 정답이므로 number의 수를 바꿔준다

위의 모든 조건이 해당되지 않으면

그 다음 수로 넘어간다

맨위에는 number의 수보다 index가 넘지 못하게 했는데 가끔 넘어가는게 있기 때문이다

DP는 현재의 값이 나머지가 0인 정답이면 그때부터 number를 바꾸고 1을 return하여 정답임을 알린다

정답이 아니라면 0을 리턴하고 DP를 반복한다

number를 바꾸면서 내려오는 것은

만약 5자리의 숫자가 들어왔을때

앞의 3자리만 바뀌었다고 하더라도

굳이 뒤의 두자리를 따로 수정할 필요없이 바로 출력을 하면 정답이 된다

small_input.txt만 풀어봐서 서버에서는 돌려볼 수 없었지만

생각보다 빠르게 풀어서 기분이 좋다