SWEA 1225 : 암호생성기

접근방법

---

기본적인 접근방법

큐를 사용한다.

 

추가적인 접근방법

규칙을 찾는다.

기본적인 접근방식도 있지만 이 문제의 규칙을 찾아서 연산 횟수를 줄이는 방식을 쓴다.

모든 감소시키는 수는 1, 2, 3, 4, 5를 반복하게 된다. 그리고 암호는 8개의 숫자로 이루어져 있다.

 

첫 번째 수	두 번째 수	세 번째 수	네 번째 수	다섯 번째 수	여섯 번째 수	일곱 번째 수	여덟 번째 수
-1	-2	-3	-4	-5	-1	-2	-3
-4	-5	-1	-2	-3	-4	-5	-1
-2	-3	-4	-5	-1	-2	-3	-4
-5	-1	-2	-3	-4	-5	-1	-2
-3	-4	-5	-1	-2	-3	-4	-5
-1	-2	-3	-4	-5	...

이해를 돕기 위해서 수를 맨 뒤로 보내지 않고 감소시키는 수를 계속 적어보았다.

표를 보면 마지막 줄이 두 번째 줄과 같은 수를 빼고 있다는 것을 볼 수 있다.

결국 이 암호생성기는 8사이클마다 같은 수를 빼고 있는 것이다.

이를 이용하면 8사이클 동안 한 수에서 총 15를 빼고 있다는 것을 알 수 있다.

 

각 수들에서 얼마를 빼야 하는지 알기 위해서 수들의 최솟값을 구한 후 그것보다 작은 15의 배수를 구한다.

(32, 35, 40, 38) -> 30이 최솟값보다 작은 15의 배수 중 제일 큰수

 

그다음 모든 수에 15의 배수를 빼준다.

(32, 35, 40, 38) -> (2, 5, 10, 8)

 

여기에서 주의할 점은 최솟값이 15의 배수가 나오는 상황이다.

최솟값이 30일 때 전체 원소마다 30을 빼주게 되면 사이클을 다 돌린 후의 원소의 값들이 나오게 된다.

이때의 값과 사이클을 하나씩 돌리면서 0 이하의 값이 만들어졌을 때 멈춘 원소들이 값이 같지 않다.

그래서 15의 배수에서 15를 뺀 값을 각각의  원소들에서 빼주어야 한다. 최솟값이 30일 경우에는 각 수에 15를 빼주게 된다.

(30, 35, 40, 38) -> (0, 5, 10, 8) X

(30, 35, 40, 38) -> (15, 20, 25, 23) 0

 

그러면 미리 돌 수 있는 사이클은 다 돌았다. 이제 직접 사이클을 돌릴 시간이다.

 

코드

---

import java.io.*;
import java.util.StringTokenizer;

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int[] code = new int[8];
		
		for (int i = 1; i <= 10; i++) {
			int minNum = Integer.MAX_VALUE, sub = 0;
			br.readLine();
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			//입력받으면서 최솟값 구하기
			for (int j = 0; j < 8; j++) {
				code[j] = Integer.parseInt(st.nextToken());
				if(code[j] < minNum) minNum = code[j];
			}
			
			//최솟값보다 작은 15의 배수 구하기
			sub = minNum/15*15;	
			if(minNum%15 == 0){sub -= 15;		
				System.out.println(i+" "+minNum);
			}
			//각 수에서 15의 배수 빼기
			for (int j = 0; j < 8; j++) {
				code[j] -= sub;
			}
			
			//0이 나올때 까지 사이클 돌기
			int minus = 0, index = -1;
			do {
				if(++minus == 6) minus = 1;
				index = (index+1)%8;
				code[index] -= minus;
			} while (code[index] > 0);
			code[index] = 0;
			
			sb.append("#"+i+" ");
			for (int j = index+1; j <= index+8; j++) {
				sb.append(code[j%8]+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}

}