문제 이해 단계 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS는 두 수열이 주어졌을 때, 두 수열의 공통이 되는 부분 수열 중 가장 긴 것을 찾는 문제이다. 가장 긴 수열의 길이를 출력하고, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지일 경우엔 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄은 출력하지 않는다. 문제 접근 단계 LCS 길이 구하기 [C++] 백준 9251 ..
문제 이해 단계 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net N개의 앱이 존재한다. N개의 앱에는 2가지 정보가 들어있는데, (사용 중인 메모리의 바이트 수, 비활성화했을 때의 비용) 2가지이다. M 바이트를 확보해야 하기 때문에, N개의 앱 중 몇 가지를 골라서 비활성화해야 한다. 이때 비활성화 했을 때의 비용을 최소화하여 M 바이트를 확보해야 한다. 최소 비용일 때를 출력하는 문제 문제 접근 단계 제한 사항 분석 앱의 개수(N)는 최대 100개..
문제 이해 단계 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net NxM 크기의 맵이 존재하고, 빨간 구슬과 파란 구슬이 존재한다. 맵의 테두리는 모두 벽으로 막혀있고, 하나의 구멍이 존재한다. 목표는 파란 구슬은 구멍은 남겨둔 채, 빨간 구슬을 구멍을 통해 빼내는 것. 할 수 있는 동작은 상하좌우로 기울이는 것이다. 기울인다는 것은 해당 쪽에 벽에 닿을 때까지 쭉 흐른다는 것. 예를 들어, 오른..
문제 이해 단계 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20 30,50}이고, 길이는 4이다. 문제 접근 단계 특이점 알아내기 가장 긴 ~ 부분 수열 시리즈 문제 항상 비슷하면서 풀이가 다른 게 해당 시리즈 특징이다. 일단 수열..
문제 이해 단계 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048이라는 게임이 존재한다. 이 게임 상하좌우 이동 중 하나를 고르는데, 한번 이동할 때 모든 블록이 해당 방향으로 벽이나 다른 블록에 부딪힐 때까지 움직인다. 이때 같은 값을 가지는 두 블록이 충돌하면 두 블록은 하나로 합쳐지면서 값도 하나로 합쳐진다. 한 번 이동할 때 이미 합쳐진 블록은 다른 블록과 다시 합쳐질 수 없다. 이러한 게임에서, Nx..
문제 이해 단계 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 높이 h와 너비 w를 가진 2차원 맵이 존재한다. 여기서 원하는 것은 문서를 최대한 많이 획득하는 것이다. '. ' : 빈 공간 ' * ' : 벽 ' $ ' : 문서 알파벳 대문자 : 잠겨 있는 문 알파벳 소문자 : 열쇠 해당 문자의 대문자에 해당하는 문을 열 수 있음 처음에는 빌딩 밖에 있고, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 그리고 같은 열쇠를 여러 번 사..
문제 이해 단계 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 팰린드롬은 좌우가 대칭되는 숫자로 이루어진 수열을 뜻한다. 예를 들어 (1,2,3,2,1), (1,3,1) (3) 등이 해당된다. N개의 수열이 주어지고, 총 M개의 (S, E) 쌍이 들어온다. 이는 S번호부터 E번호까지로 이루어진 수열이 팰린드롬인지를 판단하는 것이다. 팰린드롬이면 1, 그렇지 않으면 0을 출력한다. 문제 접근 단계 일단 제한사항부터 살펴보자. 수열의 크기 N은 최대 2,000까지이다. 정수는 최대 1..
문제 이해 단계 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 행렬 N개를 곱하는데 곱하는 순서에 따라 값이 달라진다. 행렬 N의 크기가 주어졌을 때, 곱셈 연산 횟수의 최솟값을 구하는 문제곱셈 연산을 하는 방법은 크기가 NxM인 행렬 A와 MxK인 행렬 B가 있을 때, AxB = N x M x K를 크기로 계산한 후 행렬은 N x K가 된다. 입력은 무조건 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다. 문제 접근 단계 ..