분할정복2 [BOJ] 백준 11819번: The Shortest does not Mean the Simplest 문제 Your are given integer numbers A, B and C. Output the remainder of division AB (B-th power of A) by C . 입력 The only line of the input file contains three integers: A, B, C (1 ≤ A,B,C ≤ 1018). Numbers are separated by spaces. 풀이 이 문제는 반복문을 통해 해결하려고 하면 B의 범위가 10^18까지 때문에 시간초과가 나게 됩니다. 따라서 분할정복을 통해 접근해야합니다. 처음에 10^18범위인 것을 보고 long으로 잡고 해결하려고 시도했으나 중간중간 rest*rest%C*(A%C)라는 조건에서 long의 범위를 벗어나는 것이 .. 2022. 1. 22. [BOJ] 백준 1074번: Z 문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 풀이 저는 이 문제를 처음에 배열에 담아서 모든 위치를 기록하고 풀면 어떨까? 라는 생각을 해봤습니다만 최대 범위인 N=15가 되었을 때 배열의 사이즈는 32768*32768의 범위이기에 시간제한인 0.5초만에 해결하기란 불가능하다고 생각했습니다.. 2022. 1. 8. 이전 1 다음
