[SWEA] 5658_보물상자 비밀번호

[문제]

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

 

SW Expert Academy

 

[풀이]

시뮬레이션 문제인 것 같다.

문제 조건만 잘 따져주면서 풀면 된다. 

 

N개의 숫자를 입력 받아서 사각형 각 변에 존재하는 숫자 조합 중에서 K번째로 큰 수를 구하면 된다.

(숫자 조합이 중복되는 것이 없도록 주의)

 

---

 

1. 회전하기

사각형에 존재하는 각 숫자들은 시계방향으로 한칸씩 이동한다. 

=> 총 N/4 번 회전하면 처음 상태로 돌아온다. 

 

2. 각 변에 있는 문자들의 합 구하기 

16진수이므로 N/4번째 자리수부터 16씩 곱해주어 더하여 전체 합을 구한다.

 

3. 최댓값 구하기 

2번에서 구한 값을 벡터에 넣어준다. ( 중복 없이 )

벡터에 다 넣어준 뒤  sort 함수를 사용해 K번째로 작은 수 출력.

 

 

[코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,K;
char map[4][8]={0,};
vector <int> num;

bool comp(int a, int b)
{
    return a>b;
}
void calc()
{
    int idx = N/4-1; // 2~8

    for(int i=0;i<4;i++){
     
        int sum=0;
        int tmp = 1;
        
        
        for(int j=idx;j>=0;j--){
            
            if(48<=map[i][j] && map[i][j] <=57){ //아스키코드 0~9
                sum += tmp * (map[i][j]-48);
            }
            else    sum += tmp * (map[i][j] - 55); // 아스키코드 A~F
            
            tmp *=16;
            
        }
        
        if(find(num.begin(),num.end(), sum) == num.end())   num.push_back(sum);
    }
}
void rotate()
{
    int idx = N/4-1; // 2~8
    char tmp[4]={0,};
    
    for(int i=0;i<4;i++)    tmp[i] = map[i][idx];
    
    while(idx>0){
        
        for(int i=0;i<4;i++){
            map[i][idx] = map[i][idx-1];
        }
        idx--;
    }
    
    for(int i=0;i<3;i++)    map[i+1][0] = tmp[i];
    map[0][0] = tmp[3];
    
}

void init()
{
    for(int i=0;i<4;i++){
        for(int j=0;j<8;j++)    map[i][j] = {0,};
    }
    num.clear();
    
}

int main(void)
{
    
    int T;
    cin >> T;
    
    for(int k=0;k<T;k++){
        init();
        
        cin >> N >> K;
        for(int i=0;i<4;i++){
            for(int j=0;j<N/4;j++){
                cin >> map[i][j];
            }
        }
        
        for(int i=0;i<N/4;i++){
            rotate();
            calc();
        }
        
        sort(num.begin(), num.end(),comp);
        cout << "#" << k+1 << " " << num[K-1]<<"\n";
    }
    return 0;
}

 

조언, 질문 환영입니다!

댓글 남겨주세요~