일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- r
- 다이나믹 프로그래밍
- REACT
- 다익스트라
- 삼성SW역량테스트
- 접미사 배열
- 데이터 분석
- Air Table
- jpa
- BFS
- dp
- 고속 푸리에 변환
- Cloud Pub/Sub
- Cloud Run
- 종만북
- 펜윅 트리
- JavaScript
- CI/CD
- 그리디
- LCS
- 우선순위 큐
- 수학
- ICPC
- 시뮬레이션
- 이분탐색
- 생활코딩
- 컴퓨터 구조
- 삼성 SW 역량테스트
- 백준 1753번
- Bit
- Today
- Total
코딩스토리
백준 15685번 - 드래곤 커브 본문
15685번: 드래곤 커브
첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커
www.acmicpc.net
구현과 시뮬레이션, 삼성 코테의 전형적인 유형이다.
설명은 복잡하고 어려워 보이지만 사실 풀어써보면 굉장히 간단한 문제다.
1. 0세대는 지정된 방향으로 한 칸 전진
2. 1세대 이상부터는 지금까지의 선분들을 끝점을 기준으로 모두 90도 회전
여기서 선분이라고 생각하지 않고 선분의 각 끝점이라고 생각해보면 어렵지 않다.
그럼 90도 회전은 어떻게 시켜야 하나 고민해봐야 한다.
나는 이 문제를 보고 90도 회전은 반드시 간단한 수식 하나로 나올 것이라고 생각했다.
그래서 가장 단순하고도 좋은 방법인 노가다를 통해 수식을 구했다.
한 점을 기준점을 기준으로 90도 회전시키는 수식
(해당 점의 좌표 - 기준점) -> x와 y좌표를 바꾸고 x에 -1 곱하기 -> 다시 기준점 더해주기
어떤 원리인지는.. 넘어가자^^
그럼 이제 생각해보면 당연히 재귀함수를 떠올리겠지만 난 재귀 함수를 싫어하기 때문에 간단한 반복문으로 코드를 짰다ㅎㅎ
여기서 가장 핵심은 끝점을 어떻게 판단할 것이냐이다.
그림을 열심히 그려보면 끝점은 반드시 시작점이 회전한 점임을 알 수 있다.
그렇기 때문에 새롭게 그려지는 점들을 차례로 vector에 넣는다고 했을 때, 시작점을 가장 마지막에 회전시키면 된다.
(설명이 살짝 복잡할 수 있으나 코드에 자세히 주석을 달아놓았습니다.)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
bool check[107][107];
int dx[] = { 1, 0, -1, 0};
int dy[] = { 0, -1, 0, 1};
void draw(int x, int y, int d, int g) {
// 지금까지 저장된 모든 좌표를 끝점을 기준으로
// 시계방향으로 90도 꺽은점들 check하기
vector<pii>point;
point.push_back(pii(x, y)); // 시작점 push
point.push_back(pii(x + dx[d], y + dy[d])); // 0세대
int t = 0;
while (t < g) { // 0세대 이상일 때에는
t++;
// 끝점(반드시 vector의 마지막 점임)을 제외하고 모두 커브 돌리기
int size = point.size() - 1;
int xx = point.back().first; // 기준점 x좌표
int yy = point.back().second; // 기준점 y좌표
for (int i = size -1 ; i >= 0; i--) { // 반드시 역순으로 해야됨. 끝점은 시작점을 회전시킨 점이기 때문!
// 회전시킨 좌표 = (원래 좌표 - 기준점) -> 규칙 -> + 기준점
// 이때 규칙 = x좌표와 y좌표 뒤집고 x에만 음수화
int nx = point[i].first - xx;
int ny = point[i].second - yy;
swap(nx, ny); nx *= -1; // 규칙 실행
nx += xx; ny += yy;
point.push_back(pii(nx, ny));
}
}
// 모든 점들을 체크하기
for (int i = 0; i < point.size(); i++) {
int tx = point[i].first;
int ty = point[i].second;
if (0 <= tx && tx <= 100 && 0 <= ty && ty <= 100 && check[tx][ty] == false) {
check[tx][ty] = true;
}
}
}
int solve() {
int ret = 0;
// 네 꼭짓점 모두 확인하는 함수
for (int i = 0; i <= 100; i++) {
for (int j = 0; j <= 100; j++) {
if (check[i][j] && check[i + 1][j] && check[i][j + 1] && check[i + 1][j + 1]) ret++;
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, x, y, d, g;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x >> y >> d >> g;
draw(x, y, d, g);
}
cout << solve() << "\n";
}
|
cs |
정사각형의 네 꼭짓점이 모두 드래곤 커브 안에 포함되어있는지 확인하는 방법은 solve() 함수를 확인해보면 된다.
나름 깔끔한 문제였던 것 같다
'알고리즘 > 삼성 SW 역량테스트 기출 문제' 카테고리의 다른 글
백준 14891번 - 톱니바퀴 (0) | 2021.03.24 |
---|---|
백준 17822번 - 원판 돌리기 (0) | 2021.03.19 |
백준 17144번 - 미세먼지 안녕! (0) | 2020.08.17 |
백준 16235번 - 나무 재테크 (0) | 2020.08.15 |
백준 16236번 - 아기상어 (0) | 2020.08.13 |