EQ1의 짱무말 갓잔치 EQ1의 짱무말 갓잔치

팰린드롬 관련 문제를 예전에 푼 적이 있어서 조금 더 수월하게 풀었던 것 같다. 그때는 팰린드롬인지 아닌지를 판별하는 문제였지만 이번에는 팰린드롬이 되기 위해서 숫자가 얼마나 더 필요한지에 대한 문제였다. 풀이 dp 문제는 dp를 잘 정의하면 반은 먹고 들어간다. dp [a][b] : a부터 b까지의 부분 수열을 팰린드롬으로 만들기 위해 끼워 넣어야 할 숫자의 최소 개수 dp를 잘 정의했다면 그다음은 이 dp를 어떻게 확장 또는 축소시켜나갈지를 고민하면 된다. a번째 수열의 수와 b번째 수열의 수가 같다면 dp [a][b] = dp [a+1][b-1] 팰린드롬을 만들려고 하는 것이기 때문에 시작 수와 끝 수가 같다면 범위를 줄여나갈 수 있다. 그러면 다르다면 어떻게 될까? a번째 수열의 수와 b번째 수열..

기업에 투자했을 때 보장된 이득을 볼 수 있다니! 이 얼마나 꿈같은 얘기인가~ 게다가 수익률도 기본적으로 100%가 넘는다...! 와! 샌즈! 와! 나도 할래 ㅠㅠ 풀이 만약 최대 이익만을 출력하는 문제였다면 조금 더 쉬웠을 것이다. 약간 응용된 배낭(냅색) 문제 정도? 하지만 각 기업에 투자한 액수를 출력하라는 문제 때문에 코드가 길어지고 구현이 조금 복잡해졌다. 일단 최대 금액을 구하는 것부터 해보자. 최대 금액 구하기 평소처럼 dp를 잘 정의하자. dp[n][m] : n만원으로 1번 기업부터 m번 기업까지 투자할 때 얻을 수 있는 최대 이익 dp[n][m-1]인 상황에서 m번째 회사에 invest 만큼의 금액을 투자하면 dp [n + invest][m]이 된다. dp [n + invest][m] =..

초기 조건을 좀 많이 적었다..ㅋㅋㅋ 더 깔끔하게 하는 방법이 있을 수도 있지만.. 그래도 뭐 풀었으면 된 거지 나는 지각은 마지막에 한 번 고려했다. 그래서 일단 dp를 다음과 같이 정의했다. dp [n][k] : n일 동안 k번 결석하고 개근상을 받을 수 있는 경우의 수 이런 형태의 문제는 흔하다. 연속되는 계단을 오르지 않거나 하는 문제 등 여러 곳에서 볼 수 있다. 이 경우 결석을 연속 세 번은 할 수 없다. 1. n일 째에 출석하는 경우 = dp [n-1][k] 이 경우 n-1일 동안 k번의 결석을 해야 하는데 어차피 마지막 날에 출석할 것이기 때문에 아무런 제약이 없다. 2. n일 째에 결석하는 경우 n일째에 결석하는 경우 연속으로 3번 결석할 수 있기 때문에 좀 더 세부적으로 경우를 나눠야 ..

이 문제가 약간 까다로운 이유는 고리 형태이기 때문에 처음과 끝이 이어져있기 때문이다. 그래서 인접했는지를 판단할 때 처음과 끝을 특수하게 새로 판단해줘야 하는데 나는 이 부분을 처음에는 고려하지 않고 나중에 출력할 때만 고려함으로써 깔끔하게 풀었다. 역시 dp문제이므로 dp를 잘 정의해보자. dp[n][k] : n개의 색이 일렬로 있을 때, k개의 색을 인접하지 않게 고르는 경우의 수 여기서 포인트는 문제의 상황과는 다르게 일렬로 있을 때로 dp를 설정하는 것이다. 이 dp를 구하는 방법은 어렵지 않다. n-1개의 색이 있는 상태에서 제일 끝에 하나의 색을 추가한다고 가정해보자. 그럼 상황은 두 가지로 나뉜다. 1. n번째 색을 선택하는 경우 2. n번째 색을 선택하지 않는 경우 1. n번째 색을 선택..

개인적으로는 신선했는데 struct를 알고리즘 풀면서 처음 사용했기 때문이다. 뭐 어떻게 어떻게 하면 struct를 안쓰고도 문제를 풀 수 있었겠지만 struct를 사용함으로서 상당히 깨끗해진 것 같다. 그거 이외에는 다른 동전 문제, 냅색(knapsack) 문제와 동일한 것 같다. 풀이 언제나 그랬듯이 dp문제의 난이도는 dp로 사용할 배열을 얼마나 잘 정의하느냐에 달렸다. 나는 다음과 같이 정의했다. dp[n][k] : n원을 k 단계까지의 동전을 사용해 만들 수 있는 경우의 수 임의로 단계라는 말을 사용했는데 흔히 사용하는 level의 의미라기보다는 동전의 종류를 구분하기 위해 사용했다. 먼저 제시된 동전일수록 앞단계라고 생각했다. 따라서 예제로 제시된 '5원 동전 3개, 10원 동전 2개, 1원 ..

LCS 개수 찾기의 약간 어려운 버전이라고 보면 될 것 같다. 완전히 LCS 식으로 생각해보자면 두루마리와 돌다리의 LCS의 갯수를 구하라는 문제다. 다만 돌다리를 번갈아가면서 밟아야 한다는 조건만 추가적으로 신경 써주면 된다. 따라서 기본적인 알고리즘 flow는 LCS와 동일하다. 돌다리가 2개이기 때문에 angel_dp, devil_dp처럼 2차원 배열을 두 개로 둬도 되지만 나는 하나의 배열에서 하고 싶었기 때문에 3차원 배열을 사용했다. dp[n][k]의 정의는 다음과 같다. k번째 돌다리까지 왔을 때 n번째 두루마리의 문자까지 만들 수 있는 경우의 수 dp가 증가하는 조건은 단 한가지이다. 현재 살펴보고 있는 두루마리(scroll)의 위치에 있는 문자와 살펴보고 있는 돌다리(angel 또는 de..

문제를 읽고 나서 '아! 역시 골드 1 문제구나'라는 생각이 들었다. 어렵다! 어려워! dp 문제인 것은 알겠는데 점화식이 도저히 상상이 안됐었다. 그래서 다른 분들의 블로그를 참고했다. 풀이 문제를 쉽게 풀기 위한 기본으로 전제는 이렇다. 1. 아무것도 없는 상태에서 키가 큰 순서대로 빌딩을 배치한다. 총 빌딩의 갯수가 10개였다면 높이가 10인 빌딩을 먼저 배치한 후 높이가 9인 빌딩을 배치하고 높이가 8인 빌딩을 배치하고... 그런식이다. 2. 빌딩을 배치할 수 있는 경우는 3가지로 나눈다. 제일 왼쪽에 배치, 제일 오른쪽에 배치, 그 외의 위치에 배치 3. dp[n][l][r] 이란 n개의 빌딩을 배치해서 왼쪽에서 봤을 때 l개의 빌딩이 보이고 오른쪽에서 봤을 때 r개의 빌딩이 보일 수 있는 경우..

어떤 것을 dp 배열로 저장할 것인지만 잘 정하면 어렵지 않은 문제였다. dp[n][k]? 줄어들지 않는 n자리 수 중 1의 자리가 k인 숫자의 갯수 n의 범위가 64까지이고 1의 자리의 범위는 0부터 9까지이므로 dp의 최대 크기는 dp[65][10]이면 충분하지만 for을 한 번이라도 줄이기 위해 dp[65][11]까지 만들고 11번째 열에 그 행의 합을 저장했다. 나는 기존의 줄어들지 않는 수의 마지막에 새로운 숫자를 붙이는 방식으로 자리수를 늘려나가는 방식을 생각했다. 따라서 1의 자리수를 알고 있다면 새로운 수를 붙일 때 1의 자리수보다 작지 않은 수를 붙이면 된다. 예를 들어 줄어들지 않는 5자리 숫자 중 1의 자리가 4인 수의 개수, 즉 dp[5][4]를 구하려한다고 생각해보자. 그렇다면 줄..