https://codingcompetitions.withgoogle.com/codejam/round/00000000008778ec
Spiraling Into Control
문제 요약
- 왼쪽 상단(1)부터 시계 방향으로 소용돌이 숫자, N은 홀수(<= 9999)
- 왼쪽 상단(1)에서 가운데(N^2)까지 이동
- 딱 K번을 사용해야하고 조건이 있음
- 더 큰 숫자로 이동
- 인접 차이가 1을 넘는 것을 1번 이상 사용해야함
접근법
- (y, x) => 숫자로 변환, 숫자 => (y, x)로 변환 : 쉽지 않았음
- K가 홀수이면 안됨 : 기본이 짝수이고, 왔다 갔다 하려면 짝수만큼 추가되어야함. 공식 해설에서는 체스판 설명을 함
- K < N - 1이어도 안됨 : 자명함
- 1에서 소용돌이 방식으로 이동 + 특정 시점 중앙까지 최단거리 = K 인 경우를 찾음
- 최단거리에 비해 남는 이동횟수를 처리해야하는데, 그 값을 소용돌이 위에서 이동한다고 생각함 : 1씩 늘어나니까 손해는 보지 않을 것 같음
- 특정 위치가 있다고 치면 앞 뒤를 살펴봄
- 앞 : K 에 비해 적을 것 같음
- 뒤 : K에 비해 크거나 같을 것 같음
- 이분탐색 아이디어
- 특정 위치가 여러개 있으면 가장 작은 숫자를 찾음
- 크면 중앙으로 이동할때 불편한 요소가 있음
- 특정 위치에서의 중앙으로 이동은 하드 코딩 함
- 그림을 그려 생각해보면 일부는 소용돌이로 이동하다가 이후부터 건너뛰면 됨
- 좌상 : 우/하
- 우상 : 하/좌
- 우하 : 좌/상
- 좌하 : 하/우
- 이분탐색
- x에서의 값
- x까지 소용돌이로 이동한 값 : x - 1
- x에서 가운데로 이동하는 값 : (x의 좌표 - r가운데 좌표)
- x에서의 값
- 좌표 <=> 숫자 변환
- 테두리로 분리하고, 시작값을 판단해서 일일이 이동......
Pixelated Circle
문제요약
- 픽셀이 원을 그리는데 두 가지 방식으로 그림
- R 반경 이내를 다 칠함
- R'인 테두리를 그려서 채워나감
접근법
- 작은 테케에 대해서는 직접 구현했는데, 문제 설명을 바르게 보지 못해서 힘들었음
newbieski