[ 백준 15685번 드래곤 커브 ] 문제 풀이(Java) - 삼성 SW역량테스트 기출

 

삼성 SW역량테스트 기출 '드래곤 커브' 문제를 풀어보았습니다.

 

규칙을 찾아서 0~10세대 드래곤 커브 방향을 모두 구해놓고 시작하는 게 중요한 문제입니다.

(역시 규칙 찾는 시뮬레이션 문제는 어려워,,,,)

 

 

문제보기

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

나의 풀이

 

문제 설명에 따르면, 규칙은 다음과 같습니다.

 

"K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다."

 

 

저는 드래곤 커브의 방향을 써보면서 세대가 늘어날 때 어떤 규칙이 적용될지를 고민해봤습니다.

 

간단하게 설명하기 위해 시작 방향은 0으로 고정해보겠습니다.

 

0세대 일 때   0

1세대 일 때   0   1

2세대 일 때   0   1   2   1

3세대 일 때   0   1   2   1    2    3    2    1

 

규칙이 보이시나요?

 

K세대 드래곤 커브는 K-1세대 드래곤 커브의 2배로 크기가 늘어나며, 이전 값들은 같고 뒤에 값들은 이전 값들의 90도 회전시킨 방향의 값과 같습니다.

 

3세대 드래곤 커브         0   1   2   1    2    3    2    1

 

0을 90도 회전시킨 방향은 1, 1을 90도 회전시킨 방향은 2, 2를 90도 회전시킨 방향은 3, 3을 90도 회전시킨 방향은 0이 되니 다음과 같은 규칙이 성립하는 것입니다!

 

규칙을 구했으면, 이제 배열에 값들을 저장해봅시다.

 

<배열 정의>

A[세대][시작 방향][]으로 선언한 뒤, 값을 채워줍니다.

 

이전 값들에 대해서는 복사, 이후 값들에 대해서는 해시 맵에 미리 90도 회전시킨 방향에 대한 규칙을 저장해 둔 후 그걸 이용해서 값을 구해주면 됩니다.

 

그리고 사각형의 개수를 구해주면 끝!

 

 

코드

 

//시뮬레이션 문제

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

public class N_15685 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {

			HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
			hm.put(1, 2);
			hm.put(0, 1);
			hm.put(2, 3);
			hm.put(3, 0);

			// 0~10세대 드래곤 커브 먼저 계산
			int[][][] A = new int[11][4][];

			for (int i = 0; i < A.length; i++) {
				A[i][0] = new int[(int) Math.pow(2, i)];
				A[i][1] = new int[(int) Math.pow(2, i)];
				A[i][2] = new int[(int) Math.pow(2, i)];
				A[i][3] = new int[(int) Math.pow(2, i)];

				if (i == 0) {
					A[i][0][0] = 0;
					A[i][1][0] = 1;
					A[i][2][0] = 2;
					A[i][3][0] = 3;
					continue;
				}

				// 이전 세대 값 복사
				for (int j = 0; j < A[i - 1][0].length; j++) {
					A[i][0][j] = A[i - 1][0][j];
					A[i][1][j] = A[i - 1][1][j];
					A[i][2][j] = A[i - 1][2][j];
					A[i][3][j] = A[i - 1][3][j];
				}

				// 새로운 값 저장
				int interval = A[i - 1][0].length - 1;
				for (int j = A[i - 1][0].length; j < A[i][0].length; j++) {
					A[i][0][j] = hm.get(A[i][0][interval]);
					A[i][1][j] = hm.get(A[i][1][interval]);
					A[i][2][j] = hm.get(A[i][2][interval]);
					A[i][3][j] = hm.get(A[i][3][interval]);
					interval--;
				}

			}

			int[][] B = new int[101][101]; // 드래곤 커브가 위치한 곳은 1로 표시

			int N = Integer.parseInt(br.readLine());
			for (int i = 0; i < N; i++) {
				String[] arr = br.readLine().split(" ");
				int x = Integer.parseInt(arr[0]); // 시작점
				int y = Integer.parseInt(arr[1]);
				int d = Integer.parseInt(arr[2]); // 시작방향
				int g = Integer.parseInt(arr[3]); // 세대

				B[y][x] = 1;
				for (int j = 0; j < A[g][d].length; j++) {
					if (A[g][d][j] == 0) {
						x++;
					} else if (A[g][d][j] == 1) {
						y--;
					} else if (A[g][d][j] == 2) {
						x--;
					} else if (A[g][d][j] == 3) {
						y++;
					}
					B[y][x] = 1;
				}
			}

			int cnt = 0;
			for (int i = 0; i <= 100; i++) {
				for (int j = 0; j <= 100; j++) {
					if (B[i][j] == 1 && B[i + 1][j] == 1 && B[i][j + 1] == 1 && B[i + 1][j + 1] == 1)
						cnt++;

				}
			}

			System.out.println(cnt);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

결과

 

백준 채점결과!