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

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. 문제이해 https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 정수 리스트를 구하는 것이 목표이다. 단, 정수 리스트는 음수가 아니어야 하며, 연속된 숫자들이어야 한다. 2. 문제풀이 간단한 문제인것 같지만, 조금 까다로운 문제이다. 처음에는 그저 무조건 길이가 L인 리스트를 구하는 것이라고만 생각하고 문제를 풀었는데, 실은 길이가 L이상인 리스트들 중 가장 짧은 정수 리스트를 구하는 문제였다. 즉, 문제에서 구해야..

1. 문제이해 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net N개의 단어가 주어졌을 때, 단어의 길이가 짧은것부터 정렬하는 것이 목표이다. 단, 단어의 길이가 같다면 사전순으로 정렬하며, 같은 단어는 한번만 출력한다. 2. 문제풀이 언뜻 보면 단어의 길이만 보고 정렬하면 될것같은 간단한 문제이지만, 몇가지 조건이 더해진 살짝 까다로운 문제이다. 단어의 길이가 같다면 사전순으로 정렬한다는 것과, 같은 단어는 한번만 출력한다는 점이다...

1. 문제이해 https://www.acmicpc.net/problem/2822 2822번: 점수 계산 8개 줄에 걸쳐서 각 문제에 대한 참가자의 점수가 주어진다. 점수는 0보다 크거나 같고, 150보다 작거나 같다. 모든 문제에 대한 점수는 서로 다르다. 입력으로 주어지는 순서대로 1번 문제, 2번 문 www.acmicpc.net 8개의 문제에 대한 점수가 주어진다. 참가자의 총 점수는 이 중 가장 높은 점수 5개의 합 일때, 첫째줄에 참가자의 총점, 둘째줄에 참가자가 푼 문제번호를 출력하는 것이 목표이다. 2. 문제풀이 비교적 간단한 문제이다. 입력받은 문제의 점수와 번호를 저장해, 점수가 높은 순서대로 정렬, 이중 상위 5개의 문제의 점수의 합과 번호를 차례대로 출력하기만 하면 된다. 그렇다면, 문..

1. 문제이해 https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 길이가 64cm인 막대기를 이용해 길이가 Xcm인 막대기를 만들려고 한다. 단, 막대기는 절반으로만 자를 수 있으며, 남은 길이의 합이 X보다 크면, 자르고 남은 막대는 버려야 한다. 이때, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 것이 목표이다. 2. 문제풀이 문제가 복잡해보이지만, 사실 간단한 문제이다. 처음 주어진 막대의 길이는 64cm 이고, 절반으로만..

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. 문제이해 1037번: 약수 (acmicpc.net) 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 1과 정수 N을 제외한 정수 N의 약수들을 입력받아, 정수 N을 구하는 프로그램을 구현하는 것이 목표이다. 2. 문제풀이 정수 N의 약수들 (단, 1과 자기자신은 제외) 을 입력받아 N을 구하는 것이 목표이다. 약수가 모두 주어졌으므로, 생각보다 간단한 문제이다. 예를 들어, 구하고자 하는 N이 18이라고 가정해보자. 18의 진짜 약수는 1과 18을 제외한 나머지 약수들, 2, 3, 6, 9 이다...

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)의 값을 출력하는 프로그램을 구현하는 것이 목표이다. ..