[삼성SW기출] 15685 드래곤 커브(Simulation)
2020. 2. 26. 12:39
https://www.acmicpc.net/problem/15685
15685번: 드래곤 커브
첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2,
www.acmicpc.net
시뮬레이션 문제였습니다.
방향을 숫자로 표현한게 힌트 였습니다.
각 세대별로 그려진 드래곤 커브를 숫자로 표현해보며 규칙을 찾습니다.
방향이 0일때( ->)
0세대 : 0
1세대 : 0 1
2세대 : 0 1 2 1
3세대 : 0 1 2 1 2 3 2 1
4세대 : 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1
...
규칙을 찾아보면
다음 세대는 이전 세대의 숫자들을 역순으로 뒤집고, 순차적으로 +1 해준뒤 다시 원레 이전세대의 숫자들에 더해줌으로써 탄생합니다.
0 1 2 3 각 방향 모두 적용이되며 각 방향의 세대들을 동일한 규칙으로 드래곤 커브를 그릴 수 있습니다.
직접 공책에 적어보며 풀면 이해가 더 빨리갑니다.
'Algorithm & Data Structure > SWEA' 카테고리의 다른 글
| [삼성SW기출] (야구공) (DFS, Simulation) (0) | 2020.03.05 |
|---|---|
| [삼성SW기출] 5373 큐빙 (Simulation) (0) | 2020.02.28 |
| [삼성 SW 기출][백준] 15683 감시 (Brute force, DFS) (0) | 2020.01.25 |
| [삼성 SW 기출][백준] 14891 톱니바퀴 (0) | 2020.01.23 |
| [삼성 SW 기출][백준] 14889 스타트와 링크 (DFS, Back tracking, Brute force) (0) | 2020.01.23 |