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

- 오늘의 학습 키워드 : DP

백준

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

2775번: 부녀회장이 될테야

- 공부한 내용 본인의 언어로 정리하기

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 K = Integer.parseInt(br.readLine());
      int N = Integer.parseInt(br.readLine());

      int[][] dp = new int[K+1][N];

      // 초기값 세팅
      // 0층에 사는 사람 (0층 1호 = 1명)
      for (int i=0; i<N; i++) {
        dp[0][i] = i+1;
      }
      // 1호에 사는 사람은 1명
      for (int i=1; i<=K; i++) {
        dp[i][0] = 1;
      }

      for (int i=1; i<=K; i++) {
        for (int j=1; j<N; j++) {
          dp[i][j] = dp[i][j-1] + dp[i-1][j];
        }
      }
      System.out.println(dp[K][N-1]);
    }
  }
}

 

---

백준

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

1463번: 1로 만들기

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));
    long N = Long.parseLong(br.readLine());
    System.out.println(dynamic(N, 0));
  }

  private static int dynamic(long N, int count) {
    // 1인 경우
    if (N < 2) return count;

    return Math.min(
        dynamic(N/2, (int) (count+1+(N%2))),
        dynamic(N/3, (int) (count+1+(N%3)))
    );
  }
}

---

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

https://99club.oopy.io/

99클럽-1기 모집 중