문제 이해 단계 Dp에서 흔히 볼 수 있는 k개의 동전으로 합이 n이 동전을 만드는 문제이다. 이 문제에서 다른 점은 동전마다 개수 제한이 있다는 점이다. 문제 접근 단계 일반적은 동전문제라면 이전에 계산해 놨던 결과 중에서 가장 많은 것을 찾는 방법을 사용한다. 하지만. 이 문제에서는 개수 제한이 있기 때문에 다른 방법을 사용한다. 가장 많은 것을 찾는 방법을 사용할 수 없는 이유는, 예제케이스에서 20과 15의 경우의 수를 구한다고 가정하자. 15원에서 5원이 사용되는 경우의 수는 (5x3), (5x2 + 1x5), (5x1 + 10x1)이다. 20원에서 5원이 사용되는 경우의 수는 (5x3 + 1x5), (5x2 + 10x1), (5x1 + 10x1 + 1x5)이다. 어떤 한 수를 더해서 20원이 ..
문제 이해 단계 입력으로 N 개의 숫자들이 하나씩 띄어져서 주어진다. 마지막 수 앞에는 무조건 등호(=)가 들어가고 맨 앞을 제외하고는 +나 -를 자유롭게 넣을 수 있다. 여기서 조건이 하나 주어지는데, 중간 계산 가운데에 연산 값이 0 ~ 20 사이여야 한다. 즉 음수가 나오거나 20이 넘어가면 안 된다는 점을 유의해야 한다. 이러한 조건에서 수식을 올바르게 일치시키는 경우의 수를 구하는 문제이다. 힌트를 보면 대충 무슨 소리인지 이해가 될 것이다. 문제 접근 단계 힌트라고 주긴 줬는데, 솔직히 매직아이 올 거 같아서 힌트는 생각 안 하는 게 나을 것 같다. 위의 예제들로 생각해 보자. 위에 숫자들이 너무 많은데 8이 나오도록 끝에서부터 계산한다고 생각해 보자. 8 3 2 4 8 7 2 4 0 8 = ..
문제 이해 단계 문제를 이해하는데 굉장히 헷갈렸다. 설명이 짧아서 이게 무슨 소리인가 싶어서 한참을 봤다. 두 개의 대문자 문자열이 주어지고, 그 두 문자열 중 공통 문자 중 가장 긴 수열을 구한다는 것인데 이런 것이다. 예제에서는 공통 문자가 'A, C, K, P' 총 4개인데, ACAYKP 입장에서 공통된 것을 나열해 보면 ACAKP CAPCAK 입장에서는 CAPCAK이다. 이 중에서 이 형태를 유지하면서 얻을 수 있는 가장 긴 수열은 ACAK라는 뜻이다. P를 사용하지 못하는 이유는 P를 사용하면 배열 형태가 달라지기 때문이다. 아무튼 이런 식으로 접근하면 된다. 문제 접근 단계 해당 문제는 총 2가지의 풀이법이 존재한다. 1. 논리적 풀이 2. 수학적 풀이 풀이법을 하나하나씩 풀어보겠다. 1. 논..
문제 이해 단계 N개의 물건이 주어지고 각 물건에는 무게(W)와 가치(V)가 주어진다. 최대 K만큼 들 수 있을 때, 가질 수 있는 가치의 최댓값을 구하는 문제 문제 접근 단계 이 알고리즘의 문제는 이름에서 유추해 볼 수 있듯이 배낭 알고리즘이라는 DP 알고리즘 기법 쪽에서는 좀 유명한? 그런 알고리즘이다. 우선 여기서 주어지는 변수는 무게(W), 가치(V) 총 2가지가 있다. 이 두 가지 값은 모두 변하는 값이고, 가치의 최댓값을 구하는 데에 분명 영향을 줄 것이다. 즉, 점화식은 W, V를 이용한 2차원배열로 만들어질 가능성이 높다. 이제 이 점을 유의하면서 예제를 가지고 생각해 보자!! 무게 가치 6 13 4 8 3 6 5 12 이를 위에서 아래로 순차적으로 탐색한다고 가정한다. 그러니까 무게 순으..
문제 이해 단계 n가지의 동전이 있고, 그 동전에는 각각의 가치가 있다. 그리고 그 동전들을 가지고 합이 k원을 만들어야 한다. 이때 경우의 수가 총 몇 가지가 나오는지 계산하는 문제이다. 문제 접근 단계 음 일단, 늘 그렇듯 감이 오지 않으니 예제 케이스를 가지고 나열을 해보자. 여기는 K를 기준으로 K가 1~6까지 한번 해보자 1 -> 1 1+1 / 2 -> 2 1+1+1 / 2+1 -> 2 1+1+1+1 / 2+1+1 / 2+2 -> 3 1+1+1+1+1 / 2+1+1+1 / 2+2+1 / +5 -> 4 1+1+1+1+1+1 / 2+1+1+1+1 / 2+2+1+1 / 2+2+2 / 5+1 -> 5 이런 식으로의 조합이 나온다. 이를 한번 하나의 동전끼리의 관점으로 묶어보자. 일단 K가 6일 때를 살..
문제 이해 단계 N개의 돌이 있고 마지막 돌에 도착해야 한다. 1 ~ N-1개의 돌에 정보가 주어지는데 특이한 점은 작은 점프/큰 점프가 드는 에너지가 다르다. 그리고 엄청 큰 점프는 딱 한 번만 가능하다. 이러한 조건에서 에너지를 최소한만 들여 마지막 돌에 도착해야 한다. 문제 접근 단계 전형적인 DP문제인지는 모르겠지만, 이런 DP문제를 전에 많이 풀어봐서 내 눈에는 DP문제인지 바로 보였다. 왜냐하면 Top-Bottom 방식으로 생각해 보면 구조가 보이기 때문이다. 그림으로 한번 살펴보자. 돌이 나열되어 있고, 중간에 아무런 돌 X(파란색)를 잡는다고 생각해 보자. 그렇다면 돌 X에 도달할 수 있는 경우는 어떻게 나올까? 이런 식으로 총 3가지 경우밖에 나오지 않을 것이다. 확대해서 말하면, 모든 ..
문제 이해 단계 https://www.acmicpc.net/problem/11660 NxN 크기의 맵이 주어지고, 시작 좌표와 끝좌표가 주어진다. 시작 좌표와 끝좌표를 네모를 친다고 상상하고 그 선에 닿거나 안에 있는 수들의 합을 구하는 문제이다. 문제 접근 단계 문제는 굉장히 BFS나 DFS로 풀기 좋게 생겼다. 하지만 함정일 수도 있으니 조건을 한번 읽어보자. N이 최대 1024개이고, 테스트 케이스 M이 100,000개까지 이다. NxN이기 때문에 1024x1024 대략 1,000,000개인데 최악의 경우 모든 수를 찾아봐야 한다. 그리고 M이 100,000번 할 경우, 100,000 x 1,000,000,000인데.. 음 아무리 봐도 시간초과가 뜰 거 같아서 BFS나 DFS는 아니다. 아무리 고민..
문제 이해 단계 n가지의 동전이 주어지고 그 동전에는 각각의 가치가 있다. 그 동전들을 활용하여 합을 k원으로 만든다. 이때 동전을 최소한으로 사용할 때 드는 개수를 구하는 문제. (동전은 충분히 많다는 가정) 문제 접근 단계 일단 아무런 감도 잡히지 않으니까, 예제로 어느 정도 나열을 해보자. k = 1 ~ 15 일 때까지 쭉 나열해 보면 1 / 1 + 1 / 1 + 1 + 1 / 1 + 1 + 1 + 1 5 / 5 + 1 / 5 + 1 + 1 / 5 + 1 + 1 + 1 5 + 1 + 1 + 1 + 1 / 5 + 5 / 5 + 5 + 1 12 / 12 + 1 / 12 + 1 + 1 / 5 + 5 + 5 이런 식으로 하여 k = 15일 때, 답은 5 + 5 + 5로 3이 된다. 어느 정도 규칙이 보이기..