[백준] 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.