<stdio.han>

[문제 링크]

https://www.acmicpc.net/problem/14916

[난이도]

- Silver 5

[알고리즘]

- DP

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[100001];

        dp[0] = INF;
        dp[1] = INF;
        dp[2] = 1;
        dp[3] = INF;
        dp[4] = 2;
        dp[5] = 1;

        for (int i = 6; i <= n; i++) {
            dp[i] = Math.min(dp[i - 2], dp[i - 5]) + 1;
        }
        System.out.println(dp[n] == INF ? -1 : dp[n]);
    }
}

[풀이]

DP로 문제를 풀어보았다. Bottom-up방식으로 풀었다.

1. 문제를 하위문제로 쪼갠다

dp[1] = 동전을 못거슬러줌
dp[2] = 2원짜리 하나 거슬러줌
dp[3] = 2원짜리 하나 거슬러줘도, 남은1원을 못거슬러줌
dp[4] = 2원짜리로 2개
dp[5] = 5원짜리 하나 
dp[6] = 5원짜리 하나, 남은 1원못거슬러줌 
            2원짜리 3개거슬러줌

2. 관계를 수식화
5원을 거슬러줄때랑 2원을 거슬러줄때랑을 둘 다 고려해야함

dp[n] = Math.min(dp[n-2], dp[n-5]) + 1

3. 초기값 설정

dp[0] = INF

dp[1] = INF

dp[2] = 1

dp[3] = INF

dp[4] = 2

dp[5] = 1

[출처]

https://tang25.tistory.com/entry/%EC%9E%90%EB%B0%94%EB%B0%B1%EC%A4%80-9625%EB%B2%88-%EA%B1%B0%EC%8A%A4%EB%A6%84%EB%8F%88%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%EC%97%84%ED%83%B1

[문제 링크]

https://www.acmicpc.net/problem/9655

[난이도]

- Silver 5

[알고리즘]

- DP

[코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 1;
        for (int i = 4; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 3]) + 1;
        }
        if (dp[n] % 2 == 0) {
            System.out.println("CY");
        } else {
            System.out.println("SK");
        }
    }
}

[풀이]

DP를 푸는 순서

1. 상태 결정

• dp[1] : 돌이 1개 있으면 상근이가 먼저 1개를 가져가므로 상근이 승리
• dp[2] : 상근이가 1개를 가져가고 남은 1개를 창영이가 가져가므로 창영 승리.
• dp[3] : 상근이가 처음부터 3개를 가져가면 상근 승리
• dp[4] : 상근이가 처음에 1개를 가져가면 창영이가 3개를 가져가서 창영 승리. 상근이가 처음에 3개를 가져가면 창영이가 1개를 가져가서 창영 승리.
• dp[5] : 상근이가 처음에 1개를 가져가면 창영이가 1개를 가져가든 3개를 가져가든 3개나 1개가 남아 상근이가 나머지를 가져가면 상근 승리. 상근이가 처음에 3개를 가져가면 창영이는 1개밖에 못가져가므로 나머지 1개를 상근이가 가져가 상근 승리.
•  

2. 관계를 수식화

• 돌을 1개를 가져가는 경우와 3개를 가져가는 경우 둘 다 고려해 최소값을 구한다.
• dp[n] = Math.min(dp[n-1], dp[n-3]) + 1
• dp[n] 이 홀수면 상근 승리, 짝수면 창영 승리

3. 초기값 정하기

• dp[1] = 1
• dp[2] = 2
• dp[3] = 1

[출처]

https://propercoding.tistory.com/21

[문제 링크]

https://www.acmicpc.net/problem/1010

[난이도]

- Silver 5

[알고리즘]

- DP

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int[][] dp = new int[30][30];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(st.nextToken());

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            // M개중 N개를 뽑는 경우이므로 nCr 에서 n = M, r = N 이다.
            int N = Integer.parseInt(st.nextToken()); // N = r
            int M = Integer.parseInt(st.nextToken()); // M = n

            sb.append(combi(M, N)).append("\n");
        }
        System.out.println(sb);
        br.close();
    }

    static int combi(int n, int r) {

        // 이미 계산해놓은 값이 있을 경우 바로 반환
        if (dp[n][r] > 0) {
            return dp[n][r];
        }

        // 2번 성질
        // n과r이 같거나 r==0 이면 1이다
        if (n == r || r == 0) {
            return dp[n][r] = 1;
        }

        // 1번 성질
        // nCr = n-1Cr-1 + n-1Cr 이다.
        return dp[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
    }
}

[풀이]

1번 성질 

n개 중에 r개를 뽑는 방법

2번 성질

        if (dp[n][r] > 0) {
            return dp[n][r];
        }

이미 계산해놓은 nCr이 있을 경우 그 값을 그대로 사용한다.

[출처]

https://st-lab.tistory.com/194

자바의 데이터 타입은 크게 두 가지로 나눌 수 있다. int, double, boolean 같은 기본 타입과 String, List 같은 참조 타입이다. 각각의 기본 타입에는 대응하는 참조 타입이 하나씩 있으며, 이를 박싱된 기본 타입이라고 한다. int, double, boolean에 대응하는 박싱된 기본 타입은 Integer, Double, Boolean 이다.

박싱된 기본 타입에 == 연산자를 사용하면 오류가 일어난다.

기본 타입과 박싱된 기본 타입을 혼용한 연산에서는 박싱된 기본 타입의 박싱이 자동으로 풀린다.

핵심 정리 : 기본 타입과 박싱된 기본 타입 중 하나를 선택해야 한다면 가능하면 기본 타입을 사용하라. 기본 타입은 간단하고 빠르다. 박싱된 기본 타입을 써야 한다면 주의를 기울이자. 오토박싱이 박싱된 기본 타입을 사용할 때의 번거로움을 줄여주지만, 그 위험까지 없애주지는 않는다. 두 박싱된 기본 타입을 == 연산자로 비교한다면 식별성 비교가 이뤄지는데, 이는 여러분이 원한게 아닐 가능성이 크다. 같은 연산에서 기본 타입과 박싱된 기본 타입을 혼용하면 언박싱이 이뤄지며, 언박싱 과정에서 NullPointerException을 던질 수 있다. 마지막으로, 기본 타입을 박싱하는 작업은 필요 없는 객체를 생성하는 부작용을 나을 수 있다.

float와 double 타입은 특히 금융 관련 계산과는 맞지 않는다.

float과 double타입은 근사치 계산을 하기 때문에 정확한 값을 보장하지 않는다. 특히 금융 계산과 같이 정밀도가 중요한 작업에서는 부적합하다.

금융 계산에는 BigDecimal, int 혹은 long을 사용해야 한다.

핵심 정리 : 정확한 답이 필요한 계산에는 float나 double을 피하라. 소수점 추적은 시스템에 맡기고, 코딩 시의 불편함이나 성능 저하를 신경 쓰지 않겠다면 BigDecimal을 사용하라. BigDecimal이 제공하는 여덟가지 반올림 모드를 이용하여 반올림을 완벽히 제어할 수 있다. 법으로 정해진 반올림을 수행해야 하는 비즈니스 계산에서 아주 편리한 기능이다. 반면, 성능이 중요하고 소수점을 직접 추적할 수 있고 숫자가 너무 크지 않다면 int나 long을 사용하라. 숫자를 아홉 자리 십진수로 표현할 수 있다면 int를 사용하고, 열여덟 자리 십진수로 표현할 수 있다면 long을 사용하라. 열여덟 자리를 넘어가면 BigDecimal을 사용해야 한다.