[이것이 코딩테스트다] 7. 다이나믹 프로그래밍 - 실전 문제 풀이

이것이 취업을 위한 코딩테스트다.

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

 

 

1. 1로 만들기

import java.util.Scanner;

public class Main {

	 // 30000까지 포함이므로 30000+1하여 선언
    public static int[] d = new int[30001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        sc.close();
        
        // 다이나믹 프로그래밍 (Bottom-up 방식)
        for (int i = 2; i <= x; i++) {
            // 현재의 수에서 1을 빼는 경우
        	// 우선 1을 빼준 경우의 횟수를 넣어준다 (1을 빼기 때문에 이전 숫자의 +1을 넣어준다)
            d[i] = d[i - 1] + 1;
            
            // 현재의 수가 2로 나누어 떨어지는 경우
            if (i % 2 == 0) {
            	// 1을 빼준 경우의 횟수와 2로 나눈 경우의 횟수를 비교하여 작은 쪽을 선택한다. 
            	d[i] = Math.min(d[i], d[i / 2] + 1);
            }
               
            // 현재의 수가 3으로 나누어 떨어지는 경우
            if (i % 3 == 0) {
            	d[i] = Math.min(d[i], d[i / 3] + 1);
            }
                
            // 현재의 수가 5로 나누어 떨어지는 경우
            if (i % 5 == 0) {
            	d[i] = Math.min(d[i], d[i / 5] + 1);
            }
        }

        System.out.println(d[x]);
    }

}

 

 

2. 개미 전사

import java.util.*;

public class Main {

    // 최대 식량창고의 갯수는 100개
    public static int[] d = new int[100];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 정수 N을 입력받기
        int n = sc.nextInt();

        // 모든 식량 정보 입력받기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 다이나믹 프로그래밍 (Bottom-up 방식)
        // 2번째까지는 직접 비교
        d[0] = arr[0];
        d[1] = Math.max(arr[0], arr[1]);
        
        // 3번째 창고부터는 (2개 전 창고 기준 최대 갯수 + 현재 창고 갯수) 와 (1개 전 창고 기준 최고 갯수) 중, 큰 것을 선택한다.
        // 게산 할 떄는 만약 내가 3번 째 창고가 기준이라면 4번 째 5번 째 등 현재 창고 뒤의 창고는 없다고 가정한다.
        for (int i = 2; i < n; i++) {
            d[i] = Math.max(d[i - 1], d[i - 2] + arr[i]);
        }

        // 결과 출력
        System.out.println(d[n - 1]);
    }
}

 

 

3. 바닥 공사

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		// 입력받기 
		int N = sc.nextInt();
		int[] arr = new int[N+1];
		
		arr[1] = 1;
		arr[2] = 3;
		
		// arr[i-1] 시, 2*1 공간이 남아있으므로 2*1 타일만 넣을 수 있음 
		// arr[i-2] 시, 2*2 공간이 남아있는데 2*2 타일 하나 or 1*2 타일 2개를 채워 넣는 방법이 존재한다. 
		// arr[i-2]에서 2*1 타일은 왜 포함시키지 않는가? 2*1타일을 넣는건 결국엔 arr[i-1]과 모양이 같아지기 때문에 배제한다.
		for(int i=3;i<=N;i++) {
			arr[i] = (arr[i-1] + (arr[i-2]*2))%796796;
			
		}
		
		System.out.println(arr[N]);
	}

}

 

 

4. 효과적인 화폐 구성

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		// 가지고 있는 화폐 종류 입력
		int[] currencyArr = new int[N];
		for(int i=0;i<N;i++) {
			currencyArr[i] = Integer.parseInt(br.readLine());
		}

		// M까지의 화폐를 구성하는데 최소의 경우수를 모아둔 배열 
		int[] countArr = new int[M+1];
		// 모든 배열의 수를 99999로 설정
		Arrays.fill(countArr, 99999);
		
		countArr[0] = 0;	// 0원은 0개이므로 0으로 설정
		
		// 가지고 있는 화폐의 종류만큼 반복
		for(int i=1; i<N;i++) {
			// 지금 확인하는 화폐의 수부터 확인할 화폐의 크기까지 반복
			for(int j=currencyArr[i]; j<=M; j++) {
				// x + 현재 화폐종류 = j  가 가능하려면
				// x가 99999가 아니어야 한다. Why? 99999라면 애초에 x를 조합할 수 없기 떄문에.
				if(countArr[j-currencyArr[i]] != 99999) {
					countArr[j] = Math.min(countArr[j], countArr[j-currencyArr[i]]+1);
				}
			}
		}
		
		if(countArr[M]==99999) {
			System.out.println(-1);
		}else {
			System.out.println(countArr[M]);
		}
		
	}
}