본문 바로가기

코딩 테스트63

[백준 11052] 카드 구매하기, C++ https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 본 문제는 DP문제로 입력된 N개의 카드를 각지 위해 지불해야하는 금액의 최댓값을 출력하는 것이다. Bottom-up 방식으로 풀었다. 카드 개수 및 카드 가격 입력 d[n] = max(d[n], d[n-j] + a[j])의 형태의 점화식 정의 이때, d는 개수당 최대금액을 저장하는 배열, a는 카드의 가격을 나타내는 배열이다. 카드를 1개 살때 최대값부터 4개를 살때 최대값까지 계산 Top-down 1.. 2020. 1. 11.
[백준] 1463 - 1로 만들기, C++ https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 본 문제는 DP 문제로 D[n] = min(D[n-1], D[n/3], D[n/2]) + 1 (n이 2 또는 3으로 나눌 수 있을 때의 점화식을 정의할 수 있다. DP문제는 중복되는 계산이 여러 번 등장하여야 하고, 큰 문제를 작은 문제에서 답을 구할 수 있어야 한다. 이때, 모든 반복되는 계산은 1번만 하도록 하여 계산 속도를 높인다. n을 1로 뺀 경우의 수 계산하여 저장 n을 3으로 나눌 수 있을 때, n을 3으로 나눈 경우의 수와 1번을 비교하여 저장 n을 2로 나눌 수 있을 때, n을 2로 나눈 경우의.. 2020. 1. 10.
[백준] 17298 - 오큰수, C++ https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 본 문제는 입력의 크기가 1,000,000이므로 O(n^2)의 연산으로 해결할 수 없다. 따라서, 다른 방법으로 해결해야 하는데 stack을 이용해야 한다. stack을 사용해야 된다는 것은 알았는데, 어떻게 사용해야 할지 도저히 감이 잡히지 않았다. 정답을 보고 해결하였는데 stack에 index를 저장해야 한다. stack에 index를 저장 index에 해당하는 배열보다 큰 배열의 값이 있을 경우 정답 배.. 2020. 1. 9.
[백준] 2004 - 조합 0의 개수, C++ https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. www.acmicpc.net 본 문제는 nCm의 끝자리 0의 개수를 출력하는 문제다. 문제의 크기가 2,000,000,000 이므로 long long 자료형을 써야 하며 조합을 직접 계산해서 0의 개수를 출력하는 것은 불가능하다. 따라서, 다음과 같은 절차로 코딩을 해야 한다. 5 ~ n까지 5의 배수를 5로 나누었을 때 몫의 합 2 ~ n까지 2의 배수를 2로 나누었을 때 몫의 합 5 ~ (n-m)까지 5의 배수를 5로 나누었을 때 몫의 합 2 ~ (n-m)까지 2의 배수를 2로 나누었을 때 몫의 합 (1번의 결과) - (3.. 2020. 1. 9.
[백준 1675] 팩토리얼 0의 개수, C++ https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 본 문제는 N! 에서 뒤어서부터 0이 아닐 때까지 0의 개수를 구하는 것이다. 팩토리얼에서 N이 13만 돼도 엄청 큰 숫자다 그렇기 때문에 직접 팩토리얼을 구한 다음 0의 개수를 셀 수 없다. 따라서, 뒤에 0이 나오기 위한 조건으로 구해야 한다. 어떤 수에 10이 곱해졌을 때, 뒷자리에 0이 추가된다. 그렇기 때문에 10이 곱해지는 개수를 구해야 하는데 10은 2 * 5이고 N! 에서 2의 개수보다 5의 개수가 무조건 적게 나오기 때문에 5 ~ N까지 반복하면서 X에 5가 몇 번 .. 2020. 1. 9.
[백준 6588] 골드바흐의 추측, C++ https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모 www.acmicpc.net 본 문제는 1998 University of Ulm Local Contest G번 문제다. 1742년 골드바흐는 다음과 같은 추측.. 2020. 1. 9.

티스토리툴바