백준 2470 자바 드래곤 커브

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

15685번: 드래곤 커브

 

접근 방식

풀지 못했다.

기존에 그린 선을 그대로 90도 회전해서 다시 그려야 한다. 처음에는 재귀 문제인 줄 알고 한참을 생각했다. 답이 나오지 않아서 선을 총 몇 번 그려야 하는지 계산 해보니 2의 k승만큼 선을 그어야 하는 사실을 확인했다.

for문으로 Math.pow(2,k)로 접근해봤으나 진척이 나지 않았다. 

 

기존에 그린 선을 90도 회전해서 다시 그려야 하는 규칙을 찾았는데 도통 어떻게 그려야 할지 감이 잡히지 않았다. 

그린 선을 통채로 90도 회전해서 그린다고 생각을 했는데 답안을 보니 그 방법이 아니었다.

 

처음 그린 선을 계속해서 90도 회전하면 사각형 모양에서 무한루프 된다. 선을 그릴 때 맨 앞 선을 회전하고 그리는 방법이 아니고 맨 뒷산을 회전한 뒤 그림을 그리고 그 앞선을 또 회전해서 그리고...

이 방법을 끝날 때 까지 무한반복이었다.

 

통째로 회전한다고 생각하지 말고 문제를 잘게 잘게 쪼개서 접근했어야 답을 찾을 수 있는 문제다.  한 줄 한 줄 회전시키다 보면 규칙을 찾을 수 있는데 너무 큰 그림을 그린 것 같다.

 

 

package backjon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static boolean[][] arr = new boolean[101][101];
	//우상좌하
	static int[] dy = {0,-1,0,1};
	static int[] dx = {1,0,-1,0};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int g = Integer.parseInt(st.nextToken());
			
			draw(x,y,d,g);
		}
		
		int count = 0;
		for(int i=0; i<100; i++) {
			for(int j=0; j<100; j++) {
				if(arr[i][j] && arr[i+1][j] && arr[i][j+1] && arr[i+1][j+1]) count++;
			}
		}
		
		System.out.println(count);
		
	}

	private static void draw(int x, int y, int d, int g) {
		List<Integer> list = new ArrayList<>();
		
		list.add(d);
		for (int i = 0; i < g; i++) {
			int start = list.size()-1;
			while(start >= 0) {
				int dir = list.get(start);
				list.add((dir+1)%4);
				start--;
			}
		}
		
		arr[y][x] = true;
		for (int i : list) {
			y += dy[i];
			x += dx[i];
			arr[y][x] = true;
		}
		
	}
	
}

 

 

선을 모두 저장하고 한번에 그리므로 선의 위치를 리스트에 저장하지 말고 선의 방향을 저장한다.

그리고 초기 위치부터 방향대로 한 번에 그리는 방식으로 작성했다.