문제 URL: 7795번: 먹을 것인가 먹힐 것인가 (acmicpc.net) 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 심해에는 두 종류의 생명체 A와 B가 존재하는데 A는 B를 먹는다. 이때 A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하자. 이 문제는 이분 탐색을 이용하여 푸는 문제로 배열 A와 B를 정렬한 뒤 모든 A의 원소들에 대해서..
문제 URL: 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 집과 가장 가까운 치킨집 사이의 거리를 치킨 거리라고 할 때 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|이다. 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시킬 때 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하자. 이 문..
문제 URL: https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력하는 프로그램을 작성하자. *최장 공통 부분 문자열은 연속되어야 하지만 최장 공통 부분 수열은 연속되지 않..
문제 URL: 11052번: 카드 구매하기 (acmicpc.net) 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 카드가 1개가 포함되어 있는 카드부터 N개가 포함되어 있는 카드까지 각각의 카드팩이 존재한다. 각 카드팩의 가격이 주어질 때, 원하는 개수의 카드팩을 사는 최대 비용을 출력하는 프로그램을 작성하자. 먼저 카드팩의 가격을 arr[i]에 담고 이전 카드팩의 최대 비용인 dp[i-j]에 arr에 담긴 카드팩의 가격을 하나씩 추가해서 최댓값을 구하면 된다. ex. 카드 4개를 구매할 때 dp[3] + arr[1..
문제 URL: 9655번: 돌 게임 (acmicpc.net) 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 탁자 위에 N개의 돌이 있고 상근이와 창영이가 번갈아가면서 돌을 가져간다. 돌을 1개 또는 3개 가져갈 수 있다고 할 때, 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 상근이의 차례가 선으로 두 사람이 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하자. 게임에서 돌을 1개 또는 3개만 가져갈 수 있으므로 처음에 주어진 n이 홀수라면 상근이가 이기게 되며, 짝수라면 창영이가 이기게 된다. 이에 따른 코드는 아래 과 같다. 이 문제는 다이나믹 프로그래밍을 이용하여 풀 수도 있었다. 게임에서 두 사람이 번갈아가며 ..
문제 URL: https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 위 문제는 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하는 문제로, 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력하도록 해야 했다. 2*n까지 타일을 채우는 방법을 점화식으로 나타내면 다음과 같이 나온다. dp[n-1]+2*dp[n-2] 따라서, dp[1]과 dp[2]를 이용하여 2*n까지의 타일을 채우는 식을 세워주면 된다. #in..
문제 URL: https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 이 문제는 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하는 문제로, 삼각형의 제일 밑에서 두 수를 비교하면서 둘 중에 큰 값을 위에 있는 값에 누적시키면 마지막 배열[0][0]에 원하는 결과가 나오게 된다. #include #include using namespace std; int n; int dp[500][500]; int main() { cin >> n;..
문제 URL: https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 위 문제는 재귀적인 패턴으로 별을 찍는 문제로 3의 거듭제곱으로 N이 주어졌을 때 패턴에 따라 별을 출력해야 한다. N = 3일때 패턴 중 비어있는 공간의 규칙을 찾아보면 행과 열이 3으로 나누었을 때 1이 남는다는 규칙이 보인다. 위 규칙을 토대로 N이 9 이상일 때를 살펴보면 비어있는 공간이 3x3의 모형을 띄게 된다. 따라서 (i / 3) % 3 ==..
문제 URL: https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 위 문제는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색할 때 r행 c열을 몇 번째로 방문했는지 출력하는 문제로 분할 정복과 재귀를 이용하는 문제이다. 문제를 풀기 위해 가장 먼저 한 일은 r과 c에 따라 4등분으로 영역을 나누는 일이었다. 한 영역은 전체의 1/4이기 때문에 어떤 영역에 r과 c가 위치한다면 그 영역의 이전 영역 칸 수들을 정답 ans에 모두 더해주..
문제 URL: https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 위 문제는 m개의 리모컨 버튼이 고장났을 때 원하는 채널까지 최소한으로 이동하기 위해서는 몇 번 움직여야 하는지를 출력하는 문제로 브루트포스 알고리즘을 이용하는 문제이다. 먼저 +/-로만 갈 수 있는 횟수를 최솟값으로 잡아놓고 check()함수를 통해 현재 숫자가 고장난 버튼이 포함되지 않은 숫자일 경우에 최솟값과 이동 횟수 비교를 진행한다. 이때, 500,000이 ..
