초보 개발자의 이야기, 릿허브

1. 문제이해 https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net 다음과 같은 피보나치 함수를 koong(n) (꿍 피보나치) 라고 할 때, 입력받은 n번째 꿍 피보나치를 출력하는 프로그램을 만드는 것이 목표이다. n 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4) 2. 문제풀이 간단한 DP문제이다. 사실 친..

1. 문제이해 https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 상근이는 길을 걷다가, 신기한 기계를 발견했다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었고, 버튼을 누르면, 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다. 버튼을 K번 눌렀을 때, 화면에 A와 B의 개수를 구하는 것이 목표이다. 2. 문제풀이 A와 B의 갯수를 찬찬히 살펴보면 바로 규칙을 찾을 수 있는 간단한 DP문제이다. 아래 표를 살펴보자. 버튼..

1. 문제이해 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 0과 1로만 이루어져있으면서, 아래 조건을 만족하는 수를 이친수라고 한다. N이 주어질 때, N자리 이친수의 개수를 구하는 것이 목표이다. 1. 이친수는 0으로 시작하지 않는다. 2. 이친수에서는 1이 연속으로 2번 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 2. 문제풀이 다이나믹 프로그래밍 문제이다. 처음 문제를 봤을 때 든 생각은, 1과 0 을 적절히 ..

1. 문제이해 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net n개의 정수로 이루어진 수열이 주어진다. 이 중 연속된 몇 개의 숫자를 선택해 구할 수 있는 합 중 최댓값을 출력하는 것이 목표이다. 2. 문제이해 저는 시간초과가 너무 싫어요...^^ 문제풀이를 보시는 분들이라면 아마 아시겠지만, 역시나 모든 경우의 수를 따져 합을 비교하고 구하면 시간초과가 발생한다. 필자는 첫 번째로 이중 for문을 통해 모든 경우의 합을 구하고 비교했으나, 시간초과가 발..

1. 문제이해 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net n잔의 포도주와 각 포도주의 양이 주어질 때, 최대로 마실 수 있는 포도주의 양을 구하는 것이 목표이다. (단, 선택한 포도주는 모두 마셔야 하며, 연속으로 3잔을 모두 마실 수 없다.) 2. 문제풀이 연속한 3잔을 마시지 않는 조건을 포함해, 최대로 마실 수 있는 포도주의 양을 구하는 문제이다. 문제의 뉘앙스만 봐도 이제는 DP문제임을 짐작 할 수 있다... n번째 포도주의 양을 w..

1. 문제이해 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 주어진 n에 대해 2×n 크기의 직사각형을 1×2, 2×1, 2×2 타일로 채우는 방법의 수를 구하는 것이 목표이다. 단, 방법의 수를 10,007로 나눈 값을 출력해야 한다. 2. 문제풀이 이전에 풀이했던 11726번 문제와 거의 동일한 문제이다. 단, 하나의 조건이 추가되었는데, 바로 2×2 타일이다. 이전에는 1×2, 2×1 타일만을 가지고 타일링을 했다면, 이번에는 2×2 의 경우도 고려해주어야 한다. 풀..

1. 문제이해 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 정수 삼각형은 위 그림과 같이 i번째 줄에 i개의 정수로 이루어진 삼각형이다. 삼각형의 크기 n이 주어지고 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로에 있는 수의 합을 구하는 것이 목표이다. 단, 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. (삼각형의 크기(n)는 1 이상 500 이하이며, 삼각형을 이루고..

1. 문제이해 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집의 수(N)와 각 집을 빨강(R), 초록(G), 파랑(B)으로 칠하는 비용이 주어진다. 다음과 같은 조건을 만족하면서, 모든 집을 칠할 수 있는 최소비용을 구하는 것이 목표이다. 1. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. 2. N번 집의 색은 N - 1번 집의 색과 같지 않아야 한다. 3. i(2 ≤ i ≤ N-1)번 집의 색은 i - 1번, i..

1. 문제이해 11726번: 2×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 주어진 n에 대해 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 것이 목표이다. 단, 방법의 수를 10,007로 나눈 값을 출력해야 한다. 2. 문제풀이 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제이다. 아래 그림을 통해 n이 1일때부터 하나씩 증가해가며 타일을 채우는 방법을 알아보자. 위 그림을 통해, n번째 타일을 채우는 경우의 수 = (n - 1)번..

1. 문제이해 13699번: 점화식 (acmicpc.net) 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 아래와 같은 점화식에 의해 정의된 수열 t(n)이 있다. t(0) = 1; t(n) = t(0) * t(n-1) + t(1) * t(n-2) + ... + t(n-1) * t(0) n이 주어질때, t(n)의 값을 출력하는 프로그램을 구현하는 것이 목표이다. ..