PS

백준 / 그리디 알고리즘 / 11047번 / 동전 0 / C++

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 예제 입력 1 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 출력 1 6 예제 입력 2 10 4790 1 5 10 50 ..

CodeUp / Recursion(재귀) / 4564번 / 계단 오르기 / C++

문제 설명 문제4) 계단오르기 계단 오르기 게임은 계단 아래 시작점부터 계단꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10+20+25+20=75점이 된다. 계단을 오르는 데는 다음과 같은 규칙이 있다. (1) 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. (2) 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다. (3) 마지막 도착 계단은 반드시 밟아야 한..

CodeUp / Recursion(재귀) / 3733번 / 우박수 길이(3n + 1)(large) / C++

문제 설명 콜라츠의 추측, 3n+1 문제, 우박수 문제라고 불리는 이 문제는 다음과 같다. 1, 어떤 자연수 n이 입력되면, 2. n이 홀수이면 3n+1을 하고, 3. n이 짝수이면 n/2를 한다. 4. 이 n이 1이 될때까지 2~3과정을 반복한다. 예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다. 여기서 5가 1이되기 위해 6개의 숫자를 나열하게 된다. 이것을 길이라고 하면 5의 길이는 6이된다. 시작수와 마지막 수가 입력되면 그 두 사이게 길이가 가장긴 우박수와 그 길이를 출력하시오. 입력 두 자연수 a, b가 공백으로 분리되어 입력된다. ( 1 a >> b; for (int i = a; i

CodeUp / Recursion(재귀) / 3704번 / 계단 오르기2 / C++

문제 설명 n개의 계단이 있다. 어떤 사람이 계단을 오르려 하는데 이 사람은 계단을 한번에 1계단 2계단 또는 3계단씩 오를 수 있다. 이 사람이 계단을 오를수 있는 경우의 수를 1000으로 나눈 나머지를 구하여라 입력 계단의 수 n이 입력된다. ( 1 k; cout

CodeUp / Recursion(재귀) / 3702번 / 파스칼의 삼각형2 / C++

문제 설명 다음과 같은 삼각형을 파스칼의 삼각형이라고 한다. 회전 변환된 이 삼각형에서 (r행, c열)의 값을 알 수 있는 프로그램을 작성하시오. 행과 열은 1부터 시작한다. 입력 자연수 r과 c가 입력된다. (1 ≤ r, c ≤ 50) 출력 (r, c)의 원소 값을 100,000,000으로 나눈 나머지를 출력한다. 입력 예시 3 2 출력 예시 3 #include using namespace std; int arr[50][50] = { 0 }; int pascal(int r, int c) { if(r == 1 || c == 1) // 1행과 1열은 모두 1이므로 1을 저장한다 arr[r][c] = 1; if(arr[r][c]) // 만약 배열에 이미 저장되있을경우 그 값을 return(메모이제이션) re..

CodeUp / Recursion(재귀) / 1930번 / SuperSum / C++

SuperSumSuperSum 함수는 다음과 같이 정의된다. SuperSum(0,n)=n (n은 모든 양의 정수) SuperSum(k,n)=SuperSum(k−1,1)+SuperSum(k−1,2)+...+SuperSum(k−1,n) k와 n이 여러개 주어진다. SuperSum의 값을 각각 출력하시오. 입력 k(1n(1EOF(End Of File)이다. (입력 처리 방법) while( scanf("%d %d", &k, &n) != EOF ) printf("%d\n", SuperSum(k, n)); 출력 SuperSum(k,n)SuperSum(k,n)의 값을 각 행에 하나씩 출력한다. 입력 예시 1 3 2 3 4 10 10 10 출력 예시 6 10 2002 167960 도움말 ACM-ICPC타입의 입출력방식..