문제링크 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 위처럼 입력이 주어졌을 때 아래처럼 변의 길이를 N/2씩 나누어 가며 흰색으로 만들어진 정사각형과 파란색으로 만들어진 정사각형의 개수를 출력해야한다. 문제를 보면 잘 알겠지만 대놓고 분할정복의 방법을 사용하라고 그림까지 주어져있다. 분할정복의 자세한 내용은 알고리즘 카테고리에서 다루도록하고 간단하게 설명하면 하나의 문제를 같지만 더 작은 문제로 나눈다음 작은 문제를 해결하고 결과를 합쳐서 하나의 결과가 나오도록하게 하는 전략이..
문제링크 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2xN 크기의 직사각형을 채우는 방법은 아래와 같이 나눌 수 있다. 2x(N-1)만큼 채우고 2x1 타일을 붙인다. 2x(N-2)만큼 채우고1x2 타일을 두 개 붙인다. 2x(N-2)만큼 채우고 2x2 타일을 한 개 붙인다. 위의 내용을 점화식으로 만들면 dp[n-1] + dp[n-2]*2가 된다. 코드 1 2 3 4 5 6 7 8 ..
문제링크 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 다이나믹 프로그래밍을 사용하기 위해서는 현재 항을 어떻게 이용하여 다음 항을 찾을지에 대한 점화식을 찾는 것이 가장 중요하다. 나의 경우는 직접 그림을 그려보며 점화식을 찾아보았다. n=1 일 경우 → 1가지 n=2 일 경우 → 2가지 n=3 일 경우 → 3가지 n=4 일 경우 → 5가지 n=5 일 경우 → 8가지 인 것..
문제링크 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을..
문제링크 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋..
문제링크 3061번: 사다리 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 두 줄로 구성되어 있다. 첫 번째 줄에는 사다리 세로줄의 www.acmicpc.net 문제 상덕이는 매일 점심시간마다 무엇을 먹어야 할 지 매우 고민에 빠진다. 결국 상덕이는 사다리게임을 하기로 했다. 밥을 같이 먹는 희원이는 상덕이를 놀리고 싶은 마음에, 희원이가 원하는 대로 사다리를 그리고 싶어한다. 희원이는 상덕이를 잘 속이기 위해서, 가장 적은 가로줄로 사다리를 빨리 그리려고 한다. 예를 들어, 아래와 같은 사다리를 보자. 희원이는 이 사다리의 1번 시작점은 2번째 도착점으로, 2번 시작점은 3번째 도착점으로, 3번 시작점은 1번째 도착..
문제링크 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net 문제 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 같다. 하지만, 123과 432는 구성이 같지 않다. 입력 첫째 줄에 X가 주어진다. (1 ≤ X ≤ 999999) X는 0으로 시작하지 않는다. 출력 첫째 줄에 결과를 출력한다. 만약 그러한 숫자가 없는 경우에는 0을 출력한..
문제링크 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 문제 위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다. 창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다. 만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있..
