[JAVA] 백준 dp - 브론즈, 실버모음(24416, 1010, 9625, 2491)

 

24416 알고리즘 수업 - 피보나치 수 1 - 브론즈1

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

24416번: 알고리즘 수업 - 피보나치 수 1

 

• 그냥 하라는대로 따라가면 된다. 의사코드만 잘 구현하면 될듯
• dp가 재귀호출보다 성능이 좋다는 걸 알려주려는 듯 하다
• 한 번 구한 값을 재활용하는 dp와 달리 필요할 때마다 계속 값을 구해야하는 재귀호출이 훨씬 성능이 나쁜 것을 알 수 있음

 

풀이

class Main {
  static int cnt1 = 0;
  static int cnt2 = 0;

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

    fib1(n);
    fib2(n);

    System.out.println("" + cnt1 + " " + cnt2);
  }

  private static int fib1(int n) {
    if (n==1 || n ==2) {
      cnt1++;
      return 1;
    } else {
      return fib1(n-1) + fib1(n-2);
    }
  }

  private static int fib2(int n) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(1);
    for (int i =2; i<n; i++) {
      list.add(list.get(i-1) + list.get(i-2));
      cnt2++;
    }
    return list.get(n-1);
  }
}

• 그냥 문제 그대로 구현함

 

 

1010 다리 놓기 - 실버5

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

1010번: 다리 놓기

 

• 조합문제다 -> mCn
  • 순서가 정해져있으니, m개 사이트 중 n개만 선택하면 됨
• 팩토리얼을 어떻게 잘 구할지 생각하면 될 것 같다
• 조합공식을 까먹어서 다음과 같은 방법으로 품
  • 5C3 의 경우 5C2과 같음 -> 변경
  • 5를 하나씩 줄여가며 2번 곱함 -> 5*4
  • 2의 팩토리얼을 구함 -> 2!
  • 5*4 에 2팩토리얼을 나눔

 

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

class Main {

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

    for (int t=0; t<tcCnt; t++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      
      if (m-n < n) //5C3 -> 5C2
        n = m-n;

      //n! 구하기
      long nPac = 1;
      for (int i=2; i<=n; i++) 
        nPac *= i;
      
      long num = 1;
      int tmp = m;
      for (int i =0; i<n; i++) {
        num *= tmp;
        tmp--;
      }

      num = num/nPac;

      sb.append(num); sb.append("\n");
    }

    System.out.println(sb);
  }
}

• 사람이 풀기 쉬운 방법으로 풀었다 (고등학교 때 이렇게 풀었음)
• 하지만 이쁜 조합공식이라는 게 있다

 

출처: https://m.blog.naver.com/galaxyenergy/221565884833

• 이렇게 푸는게 훨씬 깔끔할 것 같다
• n, r, n-r의 최댓값을 구하여 팩토리얼 값을 구하고
• 각각 필요한 팩토리얼 값을 꺼내와서 사용하면 될듯

 

 

9625 BABBA - 실버5

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

9625번: BABBA

 

• 처음 A일 때부터 개수를 하나씩 세야할 것 같다
• A는 B로 바뀌고, B는 BA로 바뀌므로 
  • A의 개수는 이전값의 B의 개수
  • B의 개수는 이전값의 A의 개수+B의 개수
• 이렇게 구하면 될 듯

 

풀이

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

    int aCnt = 1;
    int bCnt = 0;

    while (cnt != 0) {
      int tmpBCnt = bCnt;
      bCnt = aCnt + bCnt;
      aCnt = tmpBCnt;

      cnt--;
    }

    System.out.println("" + aCnt + " " + bCnt);
  }
}

 

 

 

2491 수열 - 실버4

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

2491번: 수열

 

• 그냥 삭 돌면서 증가, 감소하는 구간 길이를 세면 될 것 같음

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int len = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] arr = new int[len];

    for(int i=0; i<len; i++)
      arr[i] = Integer.parseInt(st.nextToken());

    int max = 0;
    int cntAsc = 1;
    int cntDsc = 1;
    for(int i=1; i<len; i++) {
      if (arr[i-1] <= arr[i])
        cntAsc++;
      else {
        if (cntAsc > max)
          max = cntAsc;
        cntAsc = 1;
      }

      if (arr[i-1] >= arr[i])
        cntDsc++;
      else {
        if (cntDsc > max)
          max = cntDsc;
        cntDsc = 1;
      }
    }

    if (cntAsc > max)
      max = cntAsc;
    if (cntDsc > max)
      max = cntDsc;

    System.out.println(max);
  }
}

• 증가한 길이를 저장하는 cntAsc와 감소한 길이를 저장하는 cntDsc를 만든다
• 배열을 한바퀴 돌면서 증가분과 감소분 길이를 잰다
  • 만약 이전 값이 지금 값보다 작거나 같으면 cntAsc를 하나 증가시켜준다
  • 만약 이전 값이 지금 값보다 크면 지금까지 센 cntAsc과 max값을 비교하여 max를 갱신시켜주고, cntAsc를 1로 초기화한다 (나부터 세니까 1이 초기화임)
  • 감소분 길이도 위와같이 구한다
• for문이 끝나고도 cntAsc와 cntDsc를 max값과 비교하여 크면 갱신해준다 (이거 안해줘서 틀림 ㅜㅜ)

 

 

 

 

 

 

 

 

 

dp라고 해서 엄청 긴장했는데 그냥 작은 문제로 큰 문제를 구할 수 있으면 모두 다이나믹 프로그래밍인가보다.

그렇게 어렵지 않아서 다행이다! (골드 이상으로 가면 더 어려울 것 같긴하다)