드래곤 커브 (15685)
1. 문제
2. 풀이
이 문제는 커브가 생성되는 규칙을 찾아내는 문제입니다.
단순히 머릿속에서 생각하지말고 직접 종이에 써가며 규칙을 찾는 방법이 제일 빠릅니다.
각설하고, 문제에서 제시한 예시를 기반으로 제가 찾은 규칙은 이렇습니다.
세대 | 진행 방향 |
---|---|
0 | → |
1 | → ↑ |
2 | → ↑ ← ↑ |
3 | → ↑ ← ↑ ← ↓ ← ↑ |
이전 세대를 뒤에서부터 반시계 방향으로 회전시킨 방향을
다음 세대로 추가합니다.
예를 들면
1세대의 → ↑
은 뒤에서부터 반시계 방향으로 회전시키면 ← ↑
이 되고
2세대는 → ↑ ← ↑
가 됩니다.
규칙을 알았으니 계획을 세워봅시다.
- 커브 방향을 리스트에 넣고 진화 세대만큼 뒤에서부터 반시계 방향으로 회전시켜 새로 추가합니다.
- 진화를 마쳤으면 테이블에 드래곤 커브를 그립니다.
- 정사각형의 개수를 구합니다.
3. 전체 코드
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception {
final int SIZE = 101;
int[] my = {0, -1, 0, 1};
int[] mx = {1, 0, -1, 0};
boolean[][] M = new boolean[SIZE][SIZE];
List<Integer> dirs = new ArrayList<>();
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
StringTokenizer stk = new StringTokenizer(br.readLine());
int y = Integer.parseInt(stk.nextToken());
int x = Integer.parseInt(stk.nextToken());
int d = Integer.parseInt(stk.nextToken());
int g = Integer.parseInt(stk.nextToken());
// 1. 커브 방향을 리스트에 넣고 진화 세대만큼 뒤에서부터 반시계 방향으로 회전시켜 새로 추가합니다.
dirs.add(d);
for (int j = 0; j < g; j++) {
for (int k = dirs.size() - 1; k >= 0; k--) {
dirs.add((dirs.get(k) + 1) % 4);
}
}
// 2. 진화를 마쳤으면 테이블에 드래곤 커브를 그립니다.
M[y][x] = true;
for (int dir: dirs) {
y += my[dir];
x += mx[dir];
M[y][x] = true;
}
dirs.clear();
}
// 3. 정사각형의 개수를 구합니다.
int ans = 0;
for (int i = 0; i < SIZE - 1; i++) {
for (int j = 0; j < SIZE - 1; j++) {
if (M[i][j] && M[i][j + 1] && M[i + 1][j] && M[i + 1][j + 1]) {
ans++;
}
}
}
bw.write(ans + "");
bw.close();
}
}
Author And Source
이 문제에 관하여(드래곤 커브 (15685)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@front/백준-드래곤-커브-15685저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)