www.acmicpc.net/problem/18291 18291번: 비요뜨의 징검다리 건너기 강을 건너는 방법은, (1 → 4), (1 → 2 → 4), (1 → 3 → 4), (1 → 2 → 3 → 4)의 4가지이다. www.acmicpc.net 일단 N=1일 때부터 직접 계산해보면서 규칙을 찾아보았다. N=1일 때 1, N=2일 때 1, N=3일 때 2, N=4일 때 4, N=5일 때 8 ... N=1일 경우를 제외하고 2의 (N-2)제곱이 나오는 것을 확인 할 수 있었다. 단순히 print(2**(N-2))를 하면 N의 범위가 최대 10**9이므로 O(10**9)가 되어서 시간초과가 발생한다. 따라서 분할정복을 이용한 거듭제곱을 해서 시간을 줄여야 한다. # 분할정복을 이용한 거듭제곱은 따로 정리해..
# 분할정복을 이용한 거듭제곱 - C**n연산은 x를 n번 곱하므로 O(N)이지만, 이 방법을 사용하면 O(logN)에 거듭제곱 값을 구할 수 있다. - 아래 코드에서 fpow함수가 그 방법이다. - n이 1이면 그냥 C의 1제곱이므로 return C를 해준다. - n이 2이상일 때, C의 n제곱은 다음과 같다. - n이 짝수이면 윗줄의 식을 만족하고, n이 홀수이면 아래줄의 식을 만족한다. 코드로 짜면 다음과 같다. 1. 재귀사용 def fpow(C, n): if n == 1: return C else: x = fpow(C, n//2) if n % 2 == 0: return x * x else: return x * x * C 2. 반복문 사용 - n & 1은 n이 짝수이면 0이므로 False이고, n이..
https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net * 분할 정복이란? - 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 분할 정복에도 여러가지 종류가 있지만, 이 문제는 쿼드트리(quad-tree)를 통해 풀어 보았다. (https://www.acmicpc.net/problem/1992 ..
모르는 사이에 조금씩 조금씩..
