[SWEA] 1242 : [S/W 문제해결 응용] 1일차 - 암호코드 스캔
1242 : [S/W 문제해결 응용] 1일차 - 암호코드 스캔
풀이
구현
2진암호코드라는 문제에서 어려워진 버전이다.
같은 코드로 조금만 고쳐서 풀려고 했는데, 여기서 문제는 2진수를 16진수로 바꿨다는게 아니였다.
한줄에 암호코드가 두개이상 나올 수 있다는 조건이 추가되서 그냥 새로 짰다.
여러번 시도를 해봤지만, 자꾸 반례가 생겼다. 그래서 다시한번 곰곰히 문제를 살펴봤다.
‘암호’코드라는 것…그러보니 비밀이 풀렸다.
첫번째는 0으로 시작하고 마지막은 1로 끝나는 규칙. 그리고 비례식.
나에겐 까다로운 조건이 2진암호코드와 다르게 몇배씩 늘릴수가 있다는것.
하지만 몇배가 되더라도 숫자간에 비를 살펴보니 겹치는게 없었다!
0부터 연속된 개수 배열에 저장, 1부터 연속된 개수 배열에 저장을 반복하다가
4개가 되면 0부터연속,1부터연속,0부터연속,1부터연속이 될것이다.
첫번째꺼 빼고 나머지 3개 중 가장 작은 수로 모두 나눈다.
그리고 다음 숫자와 매칭시켜주면된다.
“211”,”221”,”122”,”411”,”132”,”231”,”114”,”312”,”213”,”112”
배열의 4개는 숫자 하나를 만들고, 숫자8개는 암호코드1개를 만들어준다.
그렇게 암호코드를 안겹치는것만 ans변수에 더해가면 된다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
using namespace std;
string bin[] = { "0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"};
string target[10] = { "211","221","122","411","132","231","114","312","213","112" };
string conv(string s) {
string re="";
int num;
for (int i = 0; i < s.size(); i++) {
if (s[i] >= 65) {
num = s[i] - 55;
}
else {
num = s[i] - '0';
}
re += bin[num];
}
return re;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("a.txt", "r", stdin);
int t;
cin >> t;
for (int tc = 1; tc <= t; tc++) {
int ans = 0;
///////////////////////
int n, m;
cin >> n >> m;
//암호코드 저장용(중복없애기)
vector<string> vs;
vector<string> univers;
for (int i = 0; i < n; i++) {
string str;
cin >> str;
int uniflag = 1;
for (int u = 0; u < univers.size(); u++) {
if (str == univers[u]) {
uniflag = 0;
break;
}
}
if (uniflag==0) {
continue;
}
univers.push_back(str);
//2진수로 먼저 바꾼다.
string trans = conv(str);
//연속된 1 개수세기
int cnt = 0;
int cntzero = 0;
vector<int> vi;
for (int j = 0; j < trans.size(); j++) {
if (trans[j] != '0') {
vi.push_back(cntzero);
cntzero = 0;
while (j < trans.size() && trans[j] != '0') {
cnt++;
j++;
}
cntzero++;
vi.push_back(cnt);
cnt = 0;
}
else{
cntzero++;
}
}
if (vi.empty()) {
continue;
}
vector<int> numbers;
//4개=숫자1개 , 32개=숫자8개=암호코드1개
for (int j = 0; j <= vi.size(); j+=4) {
if ( (j!=0 && j % 32 == 0) || j==vi.size()) {
string tmp = "";
for (int k = 0; k < numbers.size(); k++) {
tmp += to_string(numbers[k]);
}
int flag = 1;
for (int k = 0; k < vs.size(); k++) {
if (tmp == vs[k]) {
flag = 0;
break;
}
}
if (flag) {
vs.push_back(tmp);
int oddsum = 0;
int evensum = 0;
int last = numbers[7];
for (int k = 0; k < 7; k++) {
if (k % 2 == 0) {
oddsum += numbers[k];
}
else {
evensum += numbers[k];
}
}
int test = oddsum * 3 + evensum + last;
if (test % 10 == 0) {
ans += oddsum + evensum + last;
}
}
if (j == vi.size())
break;
numbers.clear();
}
int a = vi[j + 1];
int b = vi[j + 2];
int c = vi[j + 3];
//a,b,c중 가장 작은수로 나눠준다
int mini = min({ a, b, c });
a /= mini;
b /= mini;
c /= mini;
string find = "";
find += '0'+ a;
find += '0' + b;
find += '0' + c;
//cout << find << ' ';
for (int k = 0; k < 10; k++) {
if (find == target[k]) {
numbers.push_back(k);
break;
}
}
}
}
//////////////////////
cout << '#' << tc << ' ' << ans << '\n';
}
return 0;
}
Written on August 7, 2019