0과 1의 쉼터

풀이 분할 정복을 이용한 거듭제곱 알고리즘의 기초적인 방법으로 풀이했다. 입력된 수는 int형으로 충분히 담아낼 수 있지만, 두 수의 곱은 이를 벗어나기 때문에, long long형으로 담아주어야 한다. Test Case에 주어지는 C의 값은 결과를 int형으로 출력할 수 있게 주어지는 듯 했다. 착한 문제지 쉬운 문제는 아니다. 홀수의 경우에는 A를 한번 더 곱해서 맞춰주어야 하므로 (B%2 ? A : 1) 으로 해결했다. 소스코드 #include long long mul(int A, int B, int C) { if (B > 1) { long long temp = mul(A, B/2, C); return ((temp*temp)%C * (B%2 ? A : 1)) % C; } else return A; ..

풀이 사분면을 탐색해 방문횟수를 반환하는 방식보다는, 전체 허용 범위내 조건 충족시 출력을 하는 방식으로 풀이했다. 허용 범위가 아니라면, 다른 사분면에 있으므로 n*n을 누적해준다. 소스코드 #include int r, c, cnt; void Z(int row, int col, int n){ if (row == r && col == c){ printf("%d\n", cnt); return; } if (r >= row && c >= col && r < row + n && c < col + n) { Z(row, col, n/2); Z(row, col + n/2, n/2); Z(row + n/2, col, n/2); Z(row + n/2, col + n/2, n/2); } else cnt += n*n; } ..

풀이 입력받은 지점사이의 거리(y-x)는 다음과 같은 규칙성이 존재한다. 거리의 제곱근의 정수를 기준으로 구간이 나뉜다. (ex : 3.0 ~ 3.xx, 4.0 ~ 4.xx), 제곱근의 정수를 n이라고 한다. 거리가 n*n 일때 작동 횟수는 2n - 1번이다. (빨간색) 거리가 n*n보다 크고, n*n + n 이하일 때 작동 횟수는 2n번이다. (초록색) 거리가 n*n + n보다 크고, (n+1)*(n+1)미만 일 때 작동 횟수는 2n + 1번이다. (파랑색) 거리 작동 횟수 이동 기록 1 1 1 2 2 11 3 3 111 4 3 121 5 4 1211 6 4 1221 7 5 12211 8 5 12221 9 5 12321 10 6 123211 11 6 123221 12 6 123321 13 7 12332..

풀이 좌표를 이용해 문제를 해결하기로 했다. N = 9일 때, N(9)/3의 패턴으로 둘러싸인 공백의 좌표는 (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)이다. 이 좌표들은 N(9)/3으로 나누면, 1.xx인 점을 이용해 공백을 찍으면 된다. N(9)/3의 패턴 속의 공백들의 좌표는 (1, 1), (1, 4), (1, 7), (4, 1), (4, 4), (4, 7), (7, 1), (7, 4), (7, 7)이다. 이 좌표들은 "parameter로 받아오는 3으로 나누어진 N값"이 조건을 성립하지 않아 N = 1이 될 때까지 계속 재귀함수를 호출하며, 결국 조건을 성립해 공백을 찍으면 된다. 이외의 좌표들은 "parameter..