SWEA (1225) [S/W 문제해결 기본] 7일차 - 암호생성기 - c/c++

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14uWl6AF0CFAYD

SW Expert Academy

 

시간 제한	메모리 제한	난이도	알고리즘 분류
10초	힙, 정적 : 256 MB / 스택 : 1MB	D3	-

 

 

문제

 

 

풀이

SW EA의 문제는 전반적으로 시간 제한을 넉넉하게 주는 편이다. 때문에 백준 문제를 풀 때에 비해서는 편하게 고민했지만, 그래도 시간 초과와 메모리 문제는 항상 고민해야하므로 나름 시간을 줄일 수 있는 방향으로 풀었다.

 

우선 문제에서 주어진 예시를 공책에 다시 적으며 규칙을 찾아보았다. 숫자들을 차례때로 쭉 적어내려가다보니 다음의 규칙이 눈에 띄었다. 

• 모든 수들은 40회 단위로 모든 숫자가 -15 씩 차감된다. 
• 모든 수들은 8회 단위로 다시 원래 위치로 돌아온다.

모든 수는 동시에 1회 마다 좌측으로 한 칸씩 이동한다. 즉, 이런 식으로 40회 이동한 후 모든 수들은 처음 시작했던 위치로 되돌아가고, 처음 상태에서 -15씩 차감된 상태가 된다는 뜻이다.

 

이 규칙을 찾은 후 풀이 방법은 금방 도출됐다. 먼저 배열을 하나 만들고 여덟개의 수를 모두 저장했다.

그리고 이 수들이 80회 이동 시 마다 -30씩 차감되는 상황을 가정하여, 총 몇 번 -15점 씩 깎일 수 있는 지를 구했다. 

 

예를 들어 48, 50, 72 숫자가 들어있다면, 이 배열은 48/15=2 (실수값 무시) 이므로 80회 이동 1세트로 총 2세트 회전할 수 있는거다. (셋 중 0 이하 값이 나오기 전 멈춰야 하므로.)

 

이후 15*(세트 수) 값을 다시한번 배열의 각 수에  % 연산 해주었다.

 

그러면 모든 수가 15*(세트 수) 번 회전 한 후의 수로 맞춰진다.

 

문제의 제약 사항 중 '마지막 암호 배열은 모두 한 자리 수로 구성되어있다' 가 있으므로, 위 과정이 모두 끝나고 배열에 남은 수들은 15*(세트 수) 보다 작은 수인 동시에 30~45를 넘어가지 않을 것이라고 대략 추측했다. 

 

그렇기에 이후부터는 큰 시간이 걸리지 않을 것이라 보고 일일이 수를 옮겨주며 계산하는 방식으로 답을 구했다.

 

 

코드 작성

#include <iostream>
#define SIZE 8

using namespace std;

int num[SIZE];
int sNum[SIZE];

int main() {
    while(true) {
        int t;
        if(scanf("%d", &t)==EOF) break;
        
        int minSet = 0; //최소 몇 세트(1세트=8서클=40회 자리이동) 가능한 지 
        //수들은 40회 자리이동 할 때 마다 본래 위치로 돌아오며 모든 숫자가 -15씩 깎인다.
        for (int i = 0 ; i<SIZE ; i++) {
            scanf("%d", &num[i]);
            if (i==0) minSet=num[i]/15;  //15점 단위로 몇 회 깎일 수 있는 지의 최소 수를 구한다. 
            else if (minSet>num[i]/15) minSet = num[i]/15;
        }
        
        for (int i=0 ; i<SIZE ; i++) {
            sNum[i] = num[i]%(minSet*30);
        } // 15회 단위로 사이클 돈 후 숫자 몇 남아있는 지 계산하여 sNum 배열에 저장.
        
        
        //이 아래로는 이제 수가 그리 크지 않기 때문에 일일이 자리 옮겨주며 계산한다.
        int count=0; 
        int index=-1;
        while (true) {
            count++;
            if (count==6) count=1;
            sNum[0]-=count;
            int temp=sNum[0];
            for (int i=1 ; i<SIZE ; i++) {
                sNum[i-1] = sNum[i];
            }
            sNum[SIZE-1] = temp;
            if (sNum[SIZE-1]<=0) {
                sNum[SIZE-1] = 0;
                break;
            }
        } 
        
        printf("#%d ", t);
        for (int i=0 ; i<SIZE ; i++) {
            printf("%d ", sNum[i]);
        }
        printf("\n");
    }
}

 

 

솔직히 쉽게 풀었다고는 할 수 없을 것 같고, 풀이법도 더 쉬운 방법이 분명 있을 것 같다. 

다른 사람들의 풀이를 찾아보며 추가적으로 내용을 보충해 볼 예정이지만, 의도했던 대로 정답을 구한 것 같아 뿌듯하긴 했다.

 

END.