[BOJ]13302-리조트 dp테이블의 의미는 dp[a][b]=c라고 했을 때 'a번째 날까지 쿠폰 b개가 존재하기 위해서 필요한 최소 금액 c' 이다. 쿠폰 3개를 하루 이용권으로 교환할 수 있기 때문에 따로 처리를 해주어야 한다. 이는 28~31번째 줄에 나와있다. 처음에는 쿠폰이 3장 이상 모이자마자 사용할 수 있다고 처리해서 틀렸다. 실제로는 3장 이상을 모은 다음 날부터 사용이 가능하다. 예를 들어 [3일권][5일권]을 선택했을 때, 25000+37000-10000으로 계산했다. 왜냐하면 dp배열 상으로는 dp[8][3]이 되므로 마지막 처리에서 dp[8][3]=c -> dp[8][0]=c-10000으로 계산하는 논리였기 때문이다. 실제로는 dp[8][3]=c -> dp[9][0]=c가 되어야 ..
15673-헤븐스 키친 2 N개의 수들이 주어지고, 이 N개의 수들을 2개로 그룹지어서 2개의 그룹의 곱이 최대가 되도록 만들면 된다. (그룹의 가중치 = 그룹에 속한 수들의 합)N=10만이므로, N^2 풀이는 당연히 불가능하다. 우선 테스트케이스에서 99가 나오는 원리이다. 1,2,3 번째에서 -11, 5번째에서 -9를 선택하면 곱이 99가 되고, 이 값이 최대이다. l_max[],l_min[]배열은 왼쪽부터 보면서 누적합을 계산해 나간다. 여기서 max[]배열은 양수만 고려하므로 만약 누적합이 0보다 작아진다면 차라리 그 수를 선택하지 않는것이 더 나은 선택이므로 0이 된다. min[]배열 또한 같은 원리로 누적합이 0보다 커진다면 그냥 0으로 둔다. 그리고 maxS는 이러한 max 배열들 중에서 지..
2624-동전 바꿔주기 동전1,2 문제보다 더 까다롭다고 생각하는 문제이다. 이 문제는 동전 1처럼 목표 금액을 만들 수 있는 경우의 수를 구하는 문제인데 차이점은 동전의 개수가 제한되어 있다는 점이다(동전1 문제는 동전의 개수가 무한대라고 가정했다). 따라서 동전1의 문제에서 살짝 꼬아서 낸 문제라고 생각하면 된다. dp테이블의 의미는 동전1과 동일하지만, 1차원이 아닌 2차원 배열이 필요하다. 그 이유는 곧 설명한다.dp[a][b]=c : a번째 동전까지 봤을 때, b원을 만들 수 있는 경우의 수=c가지아래의 코드에서 반복문의 변수 j가 바로 동전의 개수가 제한되어 있기 때문에 (동전1의 코드와 비교해서)새롭게 추가된 for loop이다. j는 최대 cnt[i]만큼 증가한다. 2차원 dp가 필요한 이..
12865-평범한 배낭 전형적인 Knapsack문제이다. 각 물품마다 무게와 가중치가 주어지고 정해진 무게 안에서 가중치의 합이 최대가 되도록 만들면 된다. dp테이블의 의미는 dp[a][b]=c : a번째 물품까지 봤을 때, b이하의 무게로 만들 수 있는 최대 가중치의 합=c 이다. 물품은 모두 1개씩 밖에 존재하지 않기 때문에 2차원 dp로 디자인 해야 하는 것 같다. 문제의 디스크립션은 조금 다르지만 동전시리즈 문제랑 비슷한 느낌이다. 현재 i번재 물품까지 보고 있을 때, 현재 무게(b)로 최대의 가중치를 구하기 위해서는 기존의 (i-1)번째 까지의 물품으로 만들 수 있는 가중치의 합과 이번에 i번째 물품을 이용해서 새롭게 만들어 낼 수 있는 가중치의 합 중에서 큰 값을 dp배열에 저장하면 된다. ..
2294-동전2 역시 동전 문제이다. 동전1 문제는 a원을 만들수 있는 모든 경우의 수가 관심사였다면, 이번 문제는 최소 개수를 묻고 있다. 동전 금액과 목표 금액이 있고 동전 개수는 무한대라는 가정까지는 동전1과 같으나, 이번에는 목표 금액을 만드는 동전의 최소 개수를 묻는 문제이다. 따라서 dp테이블의 의미가 달라지는데 바로 'dp[a]=b : a원을 만들기 위해 필요한 동전의 최소 개수 b개'이다. 이러면 문제의 정답은 dp[k]가 된다.테스트케이스의 입력처럼 1,5,12원의 동전으로 총 15원을 만들 수 있는 최소 동전 개수를 알아보자. 단순하게 생각해보면 1원*15개 , 5원*3개 , 12원*1+1원*3개 ....가 있을텐데 정답은 5원*3개가 정답이다. 그럼 왜 이게 정답인지 역추적을 해보자...
2293-동전1 동전 시리즈 문제가 여러 종류가 있는데 이 문제는 동전의 개수가 무한하다는 전제 하에 목표 금액을 만들 수 있는 경우의 수를 묻는 문제이다. 테스트케이스에 나와있는 1,2,5원 3종류의 동전으로 목표 금액 10원을 만들어보자. dp테이블은 'dp[a]=b : a원을 만들 수 있는 경우의 수 b가지' 라고 정의하자. 그러므로 최종 정답은 dp[k]가 될 것이다. 초기 상태는 dp[0]=1로 두자. 0원을 만들기 위해서는 아무 동전을 사용하지 않는 경우를 1가지라고 생각하면 된다. 그 다음 현재 coin[i]원의 종류로 j원을 만들려고 한다면 그 경우의 수는 어떻게 계산해야 할까. 일단 이전 상태인 (i-1)번째까지 구했던 경우의 수에다가 이번에(i)번째를 통해서 새롭게 만들 수 있는 경우의..
2098-외판원 순회 비트마스크DP를 이용한 대표적인 문제이다. 먼저 비트마스크의 원리에 대해서 간단히 설명하자면 숫자를 통해서 메모이제이션 한다는 것이다. 이게 가능한 이유는 컴퓨터에서 정수는 0과 1의 이진수 형태로 저장되기 때문이다. 만약 메모이제이션의 수단으로 배열을 사용하게 된다면 call by reference 방식이므로 함수가 연속해서 호출되는 dfs방식에는 적절하지 않다. 반면에 int자료형은 call by value 방식이므로 함수가 여러번 호출되어도 안정성이 보장된다. 단 비트마스크를 항상 사용할 수 있는 것은 아니고 int형을 사용한다면 int는 32개의 비트로 이루어져 있으므로 n이 그보다 작아야 한다. 일반적으로 '1'은 방문함, 0'은 방문하지 않음으로 통용된다. 비트마스크에서 ..
ㄴ1102-발전소 외판원 순회 문제와 비슷한 유형인데, 차이점이라면 외판원 순회 문제는 반드시 모든 노드를 방문해야 했었다면 이 문제는 방문할 필요가 없는 노드(이미 가동되어 있는 발전소)가 존재하고, 또 p값이 n보다 작을 수 있다. 이 말은 곧 모든 노드를 방문할 필요가 없다는 뜻이다. 외판원 순회 문제의 dfs함수 구조와 dp배열이 다르다. 그 이유는 모두 '현재 위치가 어디인지 상관 없기'때문이다. 외판원 순회 문제의 경우에는 현재 자신이 어느 노드에 위치해있느냐에 따라서 갈 수 있는 지점이 달라지는 반면에, 이 문제는 가동되어 있는(visited에서 1인)노드라면 어디든지 도달 가능하기 때문이다. 따라서 굳이 현재 위치를 기록할 필요가 없고 그에 따라 dfs함수와 dp배열에도 현재위치를 기록하는..