반응형
'개미 전사' 문제에 대해서 풀어 보겠습니다. 1차원으로 나열된 메뚜기 창고 에서 각 식량의 갯수가 주어졌을 때, 최소 한칸 이상 떨어져 있어야 식량 창고를 털 수 있습니다. 이 털 수 있는 최대 식량의 갯수를 출력 하는 문제 입니다.
1. 접근
1. 짝수인 창고 칸만 털 경우
2. 홀수인 창고 칸만 털 경우
3. 두 경우 중 더 큰 경우 출력
처음에는 위와 같이 접근 했다. 하지만, 창고가 2칸 떨어져서 털 경우와 임의로 더 큰 경우가 있을수 있습니다.
public class Page220 {
//식량 창고
// N (3 <= N <= 100)
// K (0 <= K <= 1000)
//입력 예시
// 4
// 1 3 1 5
//출력 예시
// 8
public static void main(String[] args) {
int N = 4;
int[] array = {1, 3, 1, 5};
System.out.print(new Page220().solution(N, array));
}
int solution(int N, int[] array){
//1. 짝수 열씩의 총합
//2. 홀수 열씩의 총합
// 둘 총합 중의 더 큰 값 출력
int evenSum = 0;
int oddSum = 0;
for (int i = 0; i < N; i++) {
// 짝수 인 경우
if(i % 2 == 0)
evenSum = evenSum + array[i];
// 홀수 인 경우
if(i % 2 == 1)
oddSum = oddSum + array[i];
}
if(evenSum < oddSum)
return oddSum;
else
return evenSum;
}
}
따라서 이렇게 구현 하면 제대로 된 출력 결과를 얻을 수 없습니다. 이 전의 구한 최대값을 기억하고, 다음 상황에서 처한 dp[i-1]의 경우와 dp[i-2] + array[i]를 비교 하여 더 큰 값으로 d[i]를 업데이트 하는 접근으로 해결 할 수 있습니다. 따라서, dp[i] = Math.max(dp[i-1] , dp[i-2] + array[i]) 이와 같은 점화식을 세우고, 다이나믹 프로그래밍(DP) 접근 방식으로 구현 하였습니다.
public class Page220_2 {
//식량 창고
// N (3 <= N <= 100)
// K (0 <= K <= 1000)
//입력 예시
// 4
// 1 3 1 5
//출력 예시
// 8
public static void main(String[] args) {
int N = 4;
int[] array = {1, 3, 1, 5};
System.out.print(new Page220_2().solution(N, array));
}
int solution(int N, int[] array){
//1. 짝수 열씩의 총합
//2. 홀수 열씩의 총합
// 둘 총합 중의 더 큰 값 출력
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
int[] dp = new int[100];
// 다이나믹 프로그래밍(DP 보텀업)
dp[0] = array[0];
dp[1] = Math.max(array[0], array[1]);
for (int i = 2; i < N; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + array[i]);
}
return dp[N - 1];
}
}
반응형
'Algorithm' 카테고리의 다른 글
바닥 공사 - '이것이 코딩 테스트다 with 파이썬' (0) | 2020.09.01 |
---|---|
바닥 공사 - '이것이 코딩 테스트다 with 파이썬' (0) | 2020.09.01 |
두 배열의 원소 교체 - '이것이 코딩 테스트다 with 파이썬' (0) | 2020.08.31 |
게임 개발 - '이것이 코딩 테스트다 with 파이썬' (0) | 2020.08.31 |
미로 탈출 문제 (0) | 2020.08.29 |