문제링크https://www.acmicpc.net/problem/11051 문제자연수 N과 정수 K가 주어졌을 때 이항 계수 (N / K)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.여기에서 (N / K)는 아래의 수식을 의미한다.(NK)N \choose K(KN)입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)출력(N / K)를 10,007로 나눈 나머지를 출력한다.조건시간 제한 : 1s메모리 제한 : 256MB해설파스칼의 삼각형을 DP로 만들어 범위의 위험에서 안전하게 해결할 수 있다.1 : 1 1 2 : 1 2 1 3 : 1 3 3 1 4 : 1 4 6 4 1 ... 5C2 → 5번째 줄의 2번 index 값을 출력 풀이파스칼의 삼각형을 만들면 해..
문제링크https://www.acmicpc.net/problem/10872문제0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.입력첫째 줄에 정수 N(0 ≤ N ≤ 12)가 주어진다.출력첫째 줄에 N!을 출력한다.조건시간 제한 : 1s메모리 제한 : 256MB해설재귀를 이용해서 팩토리얼을 구현해보자!팩토리얼을 재귀로 구현하기 위해서는 팩토리얼 함수 안에서 팩토리얼 함수를 호출할 수 있으면 된다. 이를 생각해보면 factorial(N) = N * factorial(N-1) 으로 구현할 수 있다. factorial(0)의 값이 1이고, N이 0보다 작아질 수 없기 때문에, factorial(0) 에서 1값을 return해주면 된다. 풀이factorial 함수는 아래의 방법..
문제링크https://www.acmicpc.net/problem/1699문제어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000..
문제링크https://www.acmicpc.net/problem/11055문제수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.조건시간 제한 : 1s메모리 제한 : 256MB해설주어진 입력값 중 k 를 다..
문제링크https://www.acmicpc.net/problem/2225문제0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.입력첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.출력첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.조건시간 제한 : 2s메모리 제한 : 128MB해설N이 8이라고 가정하고 K에 따른 경우의 수를 구해보면 아래와 같다.K = 1 >> 1 8 K = 2 >> 9 0 8 / 1 7 / 2 6 / 3 5 / 4 4 / 5 3 / 6 2 / 7 1 / 8 0 ..
문제링크https://www.acmicpc.net/problem/1904문제지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0..
문제링크https://www.acmicpc.net/problem/11048문제준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.입력첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,00..
문제링크https://www.acmicpc.net/problem/11054문제수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.입력첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는..
[백준] 17298 - 오큰수
문제링크 https://www.acmicpc.net/problem/17298 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째..
문제링크https://www.acmicpc.net/problem/2293문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.입력첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.조건시간 제한 : 0.5s메모리 제한 : 4MB해설https://sihyungyou.github.io/..