[백준 11053] 가장 긴 증가하는 부분 수열, C++
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 본 문제는 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제다. 수열의 값을 저장하는 배열 a, 긴 부분 수열의 길이를 저장하는 배열 b라고 했을 때, a[i]의 이전 배열의 값과 비교하면서, d[i] 이전의 배열의 값에 1을 더한 값과 비교를 해야한다. 즉, 1 ≤ j < i 일때..
2020. 1. 12.
[백준] 2193 - 이친수, C++
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 본 문제는 0과 1로만 이루어진 수 중, 0으로 시작하지 않고, 1이 두 번 연속으로 나타나지 않는 수를 구하는 문제다. 큰 문제를 작은 ..
2020. 1. 11.
[백준 15990] 1, 2, 3 더하기 5, C++
https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 본 문제는 입력된 숫자를 1, 2, 3의 합으로 표현할 수 있는 경우의 수를 구하는 문제다. 예를 들어 7이 입력되었을 때, (합이 6이 되는 경우의 수), (합이 5가 되는 경우의 수), (합이 4가 되는 경우의 수)에 1, 2, 3을 더해서 구할 수 있다. 동일한 계산을 여러 번 해야 하며, 큰 문제를 작은 문제로 해결할 수 있기 때문에 DP로 문제를 해결할 수 있다. 문제의 조건 중 같은 수를 두 번 이상 연속해서 사용하면 안 되기 때문에, ..
2020. 1. 11.
[백준] 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.