넘치게 채우기

https://www.acmicpc.net/problem/2263BOJ - 트리의 순회문제 유형: 트리, dfs, 분할 정복문제 난이도: Gold I시간 제한: 5초메모리 제한: 128MB 문제n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력첫째 줄에 프리오더를 출력한다. 풀이중위순회의 정보는 노드들간의 좌우관계를 알려준다.후위순회에서의 마지막원소는 항상 루트노드의 값이다.즉, 루트노드를 중위순회..

https://codeforces.com/contest/2043/problem/AEducational Codeforces Round 173(Div.2) - A. Coin Transformation문제 유형: 재귀, 분할 정복시간 제한: 1초메모리 제한: 256MB 문제Initially, you have a coin with value n">n.You can perform the following operation any number of times (possibly zero):- transform one coin with value x">x, where x">x is greater than 3">3 (x>3">x>3), into two coins with value ⌊x4⌋..

https://www.acmicpc.net/problem/11444BOJ - 피보나치 수 6문제 유형: 피보나치 수, 분할 정복문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n이 주어진다. n은 ..

https://www.acmicpc.net/problem/13172BOJ - Σ문제 유형: 정수론, 분할 정복문제 난이도: Gold IV시간 제한: 1초메모리 제한: 512MB 문제실제로 존재하는지 아닌지는 차치하고, 당신에게 삼면체 주사위가 있어서 이 주사위를 굴린다고 생각해보자. 주사위를 굴렸을 때 각 면이 나올 확률은 모두 동일하게 1/3 이다. 한 면에는 1, 다른 한 면에는 2, 남은 한 면에는 4가 적혀있다고 하면 주사위를 굴렸을 때 나오게 되는 숫자의 기댓값은 과연 몇일까? 간단하게도 셋의 평균인 7/3이 될 것이다.이 문제를 조금 확장해서, "N면체 주사위의 각 면에 적힌 수가 주어졌을 때, 주사위를 굴렸을 때 각 면이 나올 확률이 모두 같다면 주사위를 굴렸을 때 나오게 되는 수의 기댓값은..

https://www.acmicpc.net/problem/1629BOJ - 곱셈문제 유형: 수학, 재귀, 분할 정복문제 난이도: Silver I시간 제한: 0.5초메모리 제한: 128MB 문제자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 풀이거듭제곱의 끝자리수 사이클을 이용하는 방법은 느리다.대신, 분할 정복을 이용하여 문제를 풀 수 있다.따로 dp테이블같은거에 저장할 필요는 없다.한 번 이외에 추가적인 인출 및 ..