허비의 기술블로그

숫자의 길이 N이 주어질 때 N의 길이로 만들 수 있는 오르막 수의 개수를 구하는 문제다. 오르막 수란 수에서 모든 인접한 숫자가 오름차순으로 연결되는 수를 말한다. 인접한 숫자는 같아도 된다. N은 최대 1000이다. ex) 1, 2, 11, 12, 123, 112는 오르막 수다. 21, 12343, 154는 오르막 수가 아니다. 시간 복잡도: O(N * 10) 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 과정 모든 경우를 탐색하는 완전 탐색으로 문제를 해결하려면 ..

카드를 총 N장 구매하려고 한다. 이때 카드의 수가 각각 1장부터 N장까지 있는 묶음의 가격이 차례대로 주어질 때, 딱 N장을 구매하기 위해 드는 비용을 최대로 하는 정답을 찾는 문제다. ex) N = 4, 카드 묶음 = [1, 5, 6, 7] 일 때 이는 1장 묶음을 사는데 드는 비용이 1, 2장 묶음을 사는데 드는 비용이 5, 3장 묶음을 사는데 드는 비용이 6, 4장 묶음을 사는데 드는 비용이 7 이 든다는 것을 의미한다. 4장을 사는데 드는 최대 비용은 2장 묶음을 2번 사서 드는 10이다. 시간 복잡도: O(N^2) 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1..

1~100,000 사이의 자연수 N을 제곱수들의 합으로 나타낼 때, 가능한 경우의 수에서 항의 최소 개수를 구하는 문제다. 시간 복잡도: O(N) 풀이 과정 어떤 규칙으로 나타낼 수 있을지 생각이 안 나서 1부터 숫자들을 제곱수로 나타내 봤다. 제곱수 하나로 만들어질 수 있는 1, 4, 9에서 수가 커질수록 1의 제곱이 1씩 붙는 경우가 많다. 하지만 8, 12처럼 뒤에 1의 제곱이 아니라 다른 수가 붙는 경우도 있어 규칙이 존재하지는 않는다. 그런데 여기서 N에 대해 제곱수의 합으로 나타내려고 할 때, 그 항의 개수는 N에서 어떤 제곱수를 뺀 값에서의 항 개수 + 1과 같다. 12의 경우를 다시 살펴보자. N = 12일 때 정답 값은 N = 8일 때 정답 값 + 1이다. 하지만 나올 수 있는 경우는 N..

길이 N이 주어질 때, 1이 2개 이상 연속해서 나오지 않으며, 길이가 N인 2진수의 개수를 구하는 문제다. 단 2진수는 1로 시작해야 한다. 시간 복잡도 : O(N) 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 방법 2진수의 길이가 1씩 늘어난다고 하면, 바로 직전에 만들었던 이친수에 0을 붙여서 이친수를 만들 수 있고, 전전에 만들었던 이친수에 01을 붙여 이친수를 새로 만들 수 있다. 이렇게 만들면 이친수가 중복 없이 생성된다. N 이친수 1 1 2 10 3 101,100 4 1001..

N의 크기가 주어질 때 2 * N 사이즈의 직사각형을 (2 X 1), (1 X 2), (2 X 2)의 직사각형으로 채우는 경우의 수를 구하는 문제다. 경우의 수를 10007로 나눈 나머지를 정답으로 출력한다. 시간 복잡도: O(N) 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 방법 N의 크기가 커질 때마다 채울 수 있는 경우의 수는 일정한 규칙을 가지고 증가한다. N이 1일 때부터 차례대로 확인해보자 N = 1일 때 N이 1일 때는 1X2 직사각형 한 개로 이루어진 경우밖에 없으므로 1이다. N=2일 때 N이 2일 때는 (1X2 사..