[ 백준 15685 : 드래곤 커브 ]
삼성 2018상반기 공채시험 기출문제다.
규칙찾기문제였고 규칙만 찾는다면 쉽게 풀 수 있는 문제다.
일단 문제가 좀 특이한데 읽어보면서 생각해봐야한다.
입력은
x,y좌표, 드래곤 커브의 방향(0:→, 1: ↑, 2: ←, 3:↓), 그리고 정해진 세대 이다.
이제 그림을 보면 한 방향에 따라 무조건 시계방향으로 90도씩 회전한다.
나는 어떻게 구현해야할지 몰라서 일단 문제에 나온 그림과 좌표를 한번 직접 써봤는데 규칙이 있었다.
처음 좌표가 0,0 이고 방향이 오른쪽이라고 생각하자.
그럼 처음 있는 선은
(0,0) - (1,0) 이렇게 만들어진다.(방향 : 0)
다음 1세대에서는
(0,0) - (1,0) - (1,-1) (방향 : 0/1)
아직 감이 안온다. 그럼 2세대도 써본다.
(0,0) - (1,0) - (1,-1) - (0,-1) - (0,-2) (방향 : 0/1/2,1)
혹시 규칙을 찾았나여?? 아직 못찾았으면 또 한번 더 세대를 진행시켜보면
(0,0) - (1,0) - (1,-1) - (0,-1) - (0,-2) - (-1,-2) - (-1,-1) - (-2,-1) - (-2,-2) (방향 : 0/1/2,1/2,3,2,1)
이런식으로 계속해서 써보면 방향부분의 규칙을 찾을 수 있다,
사실 현재 있는 선분들을 가장 마지막 좌표를 기준으로 시계방향 90도씩 계속해서 회전시키므로 무조건 방향들이 일정하게 규칙이 생길 수 있는 부분이다.
그러므로 방향을 보면
0세대: (0)
1세대: (0), (1)
2세대: (0), (1), (2,1)
3세대: (0), (1), (2,1), (2,3,2,1)
이렇게만 보면 한 세대가 지날 수록 세로 생기는 선분들은 방향이 뒤에서부터 1씩 더해짐을 볼 수 있다.
나는 여기서 그냥 벡터를 만들었고 저 방향들을 모두 넣어줬다.
그리고 초기화해놓은 mat[101][101] 배열에 dfs함수를 이용해 처음 좌표부터 저 방향에 따라 계속해서 체크를 해줬다.
모든 입력에대해 처리를 해준 후 마지막에 모든 좌표(x',y')에 대해서 ((x,y),(x+1,y),(x,y+1),(x+1,y+1)) 부분이 체크되어 있다면 답을 +1 해준다.
이 블로그 검색
피드 구독하기:
댓글 (Atom)
-
[ 백준 1024 : 수열의 합 ] 간만에 푼 백준~ 쉬운 문제라고 생각하고 풀었는데 계속 틀려서 봤더니 예외 처리를 한 개 안해준것이 있었다. 만약 이 글을 보기전에 풀었을때 채점이 60%에서 자꾸 틀린다면 90%확률로 나와 같은 실수를 ...
-
[백준 1091 : 카드 섞기 ] 이 문제도 5달 전에 풀었다가 포기했었던 문제였나보다. 오늘 틀렸던 문제 다시풀기 중 풀게 되었다. 문제를 읽는데 헷갈려서 머리카락 한 10번은 쥐어짠듯. 아마 전에 풀었을때는 P배열이 각 카드가 최후에 ...
-
아마 나와 비슷한 나이대의 학생들은 대부분 대학에서 수업을 들으면서 꾸준하게 들었을 것 같다. 물론 내가 그래서 그렇다. 4차산업~ IT의 시대~ 빅데이터~ 데이터 마이닝~ 하지만 컴퓨터 관련 전공자가 아니고 더군다나 공학 계열 전공자가 아니라...
[백준 16236] 아기 상어
[ 백준 16236 : 아기 상어 ] 2018 삼성전자 sw직무 하반기 기출문제입니다. 역대 삼성전자 기출문제가 그렇듯 역시나 BFS,DFS,완탐,DP,단순구현 입니다. 저는 문제를 단순히 BFS로 풀어갔습니다. 조건만 잘 지킨다면 한번에 ...
댓글 없음:
댓글 쓰기