[SW Expert Academy] 5658. [모의 SW 역량테스트] 보물상자 비밀번호 풀이 (C++)

2018. 9. 19 에 쓰여진 글입니다.

---

문제링크

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

SW Expert Academy

 

풀이방법

풀이방법을 설명하면 

먼저 입력받을때 16진수 문자로 입력받은 것을 arr배열에 int형으로 바꿔서 저장해줌 

1번 테케로 예를 들면 

1B3B3B81F75E 이것이 입력으로 들어오니까 

arr배열에 1 11 3 11 3 11 8 1 15 7 5 14 를 저장해줌

그리고 한칸씩 시계방향으로 돌린다고 얘기했는데 그냥 이렇게 생각하는게 편함

한변의 길이가 일단 3 이니까 

1 11 3 11 3 11 8 1 15 7 5 14 

1 11 3 11 3 11 8 1 15 7 5 14

1 11 3 11 3 11 8 1 15 7 5 14

1 11 3 11 3 11 8 1 15 7 5 14

1 11 3 11 3 11 8 1 15 7 5 14

1 11 3 11 3 11 8 1 15 7 5 14

1 11 3 11 3 11 8 1 15 7 5 14

1 11 3 11 3 11 8 1 15 7 5 14

1 11 3 11 3 11 8 1 15 7 5 14

1 11 3 11 3 11 8 1 15 7 5 14

 

이렇게 빨간색칠한 부분이 하나의 수가 될것임

그럼 solve함수에서 이 빨간칠한 수를 뽑아서 (tmp_arr)

뽑은수가 1 11 3 이라고 하면 16진수 1B3 인건데 이걸 10진수값으로 바꿔줌(sum)

그리고 그 값(sum)을 make_number 배열에 저장함. 이때 만약 make_number배열에 해당 수가 있으면 (중복이있으면)

저장하지 않음

이렇게 다 해주고 나서 내림차순으로 정렬한담에 K번째배열 (배열이므로 0부터 시작하니까 make_number[K-1]) 이 답이 되는것

결국 한줄로 정리하면 그냥 변의 길이만큼 숫자를 잘라서 16진수 숫자를 10진수로 변환해주고 그걸 저장해서 정렬하면 끝

 

모의 SW 역량테스트 문제가 6문제가 추가 됬음.

뭔가 재밌어보여서 풀어보기로! 

그 중 가장 먼저 도전한 문제 보물상자 비밀번호 ~

문제 자체는 굉장히 평이함.

다른 문제는 얼핏보니까 좀 어려워보이던데... 이문제가 제일 쉬운듯?

조만간 다른문제도 풀어봐야겠음 (시간나면...)

그럼 끄읕!

 

소스코드

#include <iostream>
#include <algorithm>    //sort 위한 헤더
#include <functional>    //greater less 위한 헤더
//5658. [모의 SW 역량테스트] 보물상자 비밀번호
using namespace std;
 
#define N_SIZE 28
 
int arr[N_SIZE];        //입력받을 배열(16진수 문자로 입력받은것을 10진수로 바꿔서 저장해주는 배열)
int make_number[N_SIZE];//각 변의 합의 경우의수 저장
int Answer;                //정답
int N, K;                
int len;                //각 변의 길이
int make_number_cnt;    //중복없이 현재 만들어진 합의 경우의 수 
 
bool check(int sum)        //만약 현재 만들어진 합이랑 같은게 있으면 false, 없으면 true
{
    for (register int i = 0; i < make_number_cnt; i++)
        if (make_number[i] == sum)
            return false;
    return true;
}
 
void solve()
{
    for (register int i = 0; i < N; i++) {
        int tmp_arr[N_SIZE];
        for (register int j = 0; j < len; j++) {
            tmp_arr[j] = arr[(i + j) % N];
        }
        /*값의 합을 저장 시작*/
        int  hex = 1;
        int sum = 0;
        for (register int j = len - 1; j >= 0; j--) {    //16진수->10진수로 변환해서 저장
            sum += (tmp_arr[j] * hex);
            hex *= 16;
        }
        /*값의 합을 저장 끝*/
        if (check(sum)){        //해당 숫자가 만들어져있지 않으면
            make_number[make_number_cnt] = sum;    //저장해주고
            make_number_cnt++;                    //갯수 증가시켜줌
        }
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    for (register int test_case = 1; test_case <= T; test_case++) {
        /*초기화,입력*/
        Answer = 0;                
        make_number_cnt = 0;
        scanf("%d %d", &N, &K);
        len = N / 4;
        char s[N_SIZE + 1] = { '\0' };
        scanf("%s", &s);
        /*16진수 문자로 들어온것을 10진수로 바꿔서 저장함*/
        for (register int i = 0; i < N; i++) {
            if ('0' <= s[i] && s[i] <= '9')
                arr[i] = s[i] - '0';
            else
                arr[i] = s[i] - 'A' + 10;
        }
        solve();    //solve함수 호출
        sort(make_number, make_number + make_number_cnt, greater<int>());    //내림차순 정리
        printf("#%d %d\n", test_case, make_number[K - 1]);                    //출력
    }
 
    return 0;
}