문제 이해 단계 https://www.acmicpc.net/problem/15486 날짜 N과 각 날마다 할 수 있는 일 Ti와 그 일을 했을 때 버는 돈 Pi가 각각 주어진다. Ti는 그 일을 할 때마다 드는 날을 뜻하며, 그 일을 하는 동안에는 다른 일을 할 수 없다. 이런 상황일 때 돈을 최대한 벌었을 때의 수익을 구하는 문제이다. 문제 접근 단계 이해부터가 살짝 복잡했는데, N일까지 일을 해서 벌 수 있는 최대수익을 D [N]이라고 하자. 이때 유의해야 할 점은 N일까지라는 것은 N일을 포함하지 않는다. 즉 1~N-1일에 한 일만 포함하는 것이다. 이를 이용해서 1일부터 살펴보자면, 1일까지 일을 해서 번 돈은 당연히 0원일 것이고(D [1] = 0) 1일 때 일해서 번 돈은 3일이 지난 4일째의..

문제 이해 단계 https://www.acmicpc.net/problem/9465 세로가 2이고 가로가 n인 스티커가 있는데 각 스티커에는 점수가 적혀있다. 스티커를 뗄 때에는 특징이 있는데 점수를 얻는 스티커의 상하좌우에 있는 스티커는 더 이상 사용 할 수 없다. 이러한 상황일 때, 얻을 수 있는 점수의 최댓값을 구하는 문제 문제 접근 단계 해당 문제를 풀기 위해서 예제로 처음부터 시뮬레이션을 돌려보도록 하겠다. 시작값 50일 때 움직일 수 있는 칸 목록이다. 이렇듯 사실상 왼쪽과 아래에 있는 10,30을 제외하면 다 움직일 수 있는 것으로 보인다. 하지만 우리는 스티커 점수의 최댓값을 구하는 것이다. 이렇듯 100, 20,10은 50뿐만 아니라 다른 수에서 접근할 수 있다. 즉 굳이 50에서 바로 접..

문제 이해 단계 https://www.acmicpc.net/problem/1890 각 칸마다 이동해야 하는 칸 수가 적혀 있고, 가장 왼쪽 위 칸에서 오른쪽 아래 칸으로 이동해야 한다. 즉, 해당 칸에 도착했을 때 0이면 움직임이 멈춘다.(더 이상 이동하지 못하기 때문) 할 수 있는 움직임은 아래로 이동하거나 왼쪽으로 이동하거나 2가지이다. 이러한 조건일 때 가장 오른쪽 아래로 이동할 수 있는 경우의 수를 구하는 문제. 문제 접근 단계 가장 오른쪽 아래로 이동할 수 있는 경우의 수를 구하는 것이기 때문에 오른쪽 아래에서부터 역으로 출발하는 걸로 생각했다. 게임판의 크기가 NxN일 때, 마지막 칸으로 움직일 수 있는 경우는 무엇이 있을까? 그림으로 생각해 보면 이런 식이 될 것이다. 이런 식으로 마지막칸에..

이해 단계 수열 문제 시리즈이다. 수열이 주어질 때 증가하는 부분 수열을 원소들을 찾는다. 그 원소들의 집합 중 합이 가장 큰 집합을 찾아 그 값을 찾아내는 문제이다. 문제 접근 단계 가장 큰 수열 ~ 문제 시리즈 상 문제를 읽지 않아도 DP로 풀어야겠구나라고 생각이 바로 들더라.. 이러면 안 되긴 하는데 너무 문제가 시리즈상으로 많이 있어서 자연스럽게 그렇게 됐다.. 그래도 이 문제가 왜 DP로 풀 수 있는지 따져보기로 했다. 이 문제의 예제로 살펴보도록 하자. {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 왼쪽부터 x = 1이라고 해서 순차적으로 올라가 보면서 생각해 보겠다. x = 1 일 때 최댓값은 1이다. x = 2 일 때, (1)(1+100)(100) 중, 최댓값은 101이다...

문제 이해 단계 수열이 주어졌을 때 위치를 가만히 둔 채로, 오름차순으로 증가하는 부분 수열은 구한다. 그때 가장 크게 증가하는 부분수열의 길이를 구하는 문제 문제 접근 단계 문제에 나와있는 예시로 생각해 보자 10 20 10 30 20 50 1번째 수(10)에서 가장 긴 부분수열의 길이는 1이다. 2번째 수까지의 경우의 수는 3가지이다. 1. 10 - 20 (2가지) 2. 20 (1가지) 3. 10 (1가지) 이때 가장 긴 부분수열은 1번째인 2이다. 3번째 수까지의 경우의 수는 1. 10 - 20 (2가지) 2. 20 - 10 (2가지) 3. 20 ... 로 2번째보다 길어지려면 20보다 수가 높아야 하는데, 그렇지 못하므로 그대로 최대 길이는 2이다. 4번째 수까지의 경우의 수는 1. 10 - 20..

문제 이해 단계 N의 길이를 가진 수열에서 최대 K개만큼 원소를 삭제할 수 있을 때, 최대한 많이 짝수끼리 연속되게 만드는 문제이다. 그때의 개수를 구하는 문제이다. 문제 접근 단계 처음에는 1차원에다가, 짝수와 홀수를 구분하여 탐색하는 BFS를 떠올렸다. 그런데 일반적인 탐색으로 하기에는 제거할 홀수의 경우의 수가 너무 많다. 그리고 그 경우의 수를 모두 체크하기엔 너무 연산이 복잡하고 또 시간이 오래 걸린다. 또한 여기서는 어떤 시작 인덱스나 숫자를 정해주지 않아서 그것 또한 찾아야 하기 때문에 이 방법은 어울리지 않는다고 생각했다. 그다음으로 떠올린 것은 다이내믹 프로그래밍이다. 왜냐하면 이런 제한시간이 짧고, 많은 경우의 수가 있는 경우에는 충분히 가능성 있기 때문이다. 연속된 짝수를 계산하기 위..

문제 이해 단계 수학에서 조합을 뜻하는 nCr에서 n과 r이 입력으로 들어올 때, 그 해답을 출력하는 문제. 문제 접근 단계 일반적으로 연산식을 구현하여 계산하라고 이 문제를 냈을 리는 없다. 예제에서 봤듯이 입력애 따라 출력이 엄청 커지는데, 연산 처리가 오래 걸려 시간초과가 뜰 가능성이 높다. 그래서 조합 공식 nCr = n-1Cr + n-1Cr-1을 메모라이즈기법(DP) 방식으로 구현하기로 하였다. d [n][m]라는 2차원 저장공간을 두고 nCr = d [n][r] 이런 식으로 연산 값을 기억해 두기로 하였다. 그런데 한 가지 문제가 생겼다. 바로 연산 값이 엄청나게 크다는 것이다. 가장 큰 자료형인 long long int가 –9,223,372,036,854,775,808 ~ 9,223,372,..

문제 이해 단계 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다. 자연수 n이 주어질 때, 최소 개수의 제곱수 합, 즉 최소한의 자연수를 사용하여 구하는 문제이다. 문제 접근 단계 제곱수라는 말과 반대되는 말은 루트이다. 4 = 2^2인데, 이때 제곱이 되는 2라는 값은 4의 루트를 씌우면 구할 수 있다. 여기서 5라는 값을 살펴보면 5의 루트를 씌우면 2.xxx 자연수 부분은 2가 된다. 해당 문제에서는 5 = 2^2 + 1^2가 되어 2가 출력될 것이다. 이런 식으로 n에다가 루트를 씌어 하나의 제곱수를 구하고, 그 수를 뺀 나머지를 또 루트를 씌우는 과정을 반복한다면? 우리는 제곱으로만 이루어진 수의 합을 구할 수 있을 것이다(1^2이 있기 때문) 15라는 숫자를 예로 들어, 그림..