99클럽 코테 스터디 32일차 TIL + DP

- 오늘의 학습 키워드 : DP

 

백준

1번 문제

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

1003번: 피보나치 함수

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  static int[][] arr;
  static int[] f;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int T = Integer.parseInt(br.readLine());

    while (T-- > 0) {
      int N = Integer.parseInt(br.readLine());
      arr = new int[N+2][2];
      f = new int[N+1];

      fibo(N);
      sb.append(arr[N][0]).append(" ").append(arr[N][1]).append("\n");
    }
    System.out.println(sb);
  }

  private static int fibo(int N) {

    // under value
    if (N == 0) {
      arr[0][0] = 1;
      arr[0][1] = 0;
      return f[0] = 0;
    } else if (N == 1) {
      arr[1][0] = 0;
      arr[1][1] = 1;
      return f[1] = 1;
    }

    if (f[N] > 0) { // 이미 값이 설정되어 있는 경우
      return f[N];
    }

    f[N] = fibo(N-1) + fibo(N-2);
    arr[N][0] = arr[N-1][0] + arr[N-2][0]; // 0 호출 횟수
    arr[N][1] = arr[N-1][1] + arr[N-2][1]; // 1 호출 횟수
    return f[N];
  }
}

---

백준

2번 문제

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

2839번: 설탕 배달

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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 result = 0;
    while (N % 5 != 0) { // 5kg 봉지에 담을 수 없는 경우
      N -= 3; // 3kg에 모두 담기
      result++;
    }

    if (N < 0) { // Nkg를 완벽하게 담을 수 없는 경우
      System.out.println(-1);
      return;
    } else {
      // 5kg에 담을 수 있는 경우 모두 담기
      result += (N / 5);
    }
    System.out.println(result);
  }
}

 

---

백준

3번 문제

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

26099번: 설탕 배달 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

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

    BigInteger N = new BigInteger(br.readLine());
    BigInteger five = new BigInteger("5");
    BigInteger value = N.remainder(BigInteger.valueOf(5));

    if (N.intValue() == 4 || N.intValue() == 7) {
      System.out.println(-1);
    } else if (value.equals(BigInteger.ZERO)) {
      System.out.println(N.divide(five));
    } else if (value.equals(BigInteger.ONE) || value.equals(BigInteger.valueOf(3))) {
      System.out.println(N.divide(five).add(BigInteger.valueOf(1)));
    } else if (value.equals(BigInteger.TWO) || value.equals(BigInteger.valueOf(4))) {
      System.out.println(N.divide(five).add(BigInteger.valueOf(2)));
    }
  }
}

---

백준

4번 문제

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

9465번: 스티커

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

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());

    while (T -- > 0) {
      int N = Integer.parseInt(br.readLine());
      int[][] arr = new int[2][N+1];
      int[][] dp = new int[2][N+1];

      for (int i=0; i<2; i++) {
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        for (int j=1; j<=N; j++) {
          arr[i][j] = Integer.parseInt(st.nextToken());
        }
      }

      // 초기값
      dp[0][1] = arr[0][1];
      dp[1][1] = arr[1][1];

      for (int i=2; i<=N; i++) {
        dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + arr[0][i];
        dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + arr[1][i];
      }
      System.out.println(Math.max(dp[0][N], dp[1][N]));
    }
  }
}

---

99클럽 1기를 수강하면서 작성한 글입니다.

https://99club.oopy.io/

99클럽-1기 모집 중