[JAVA] 백준 dp - 브론즈모음(2748 피보나치 수 2, 2775 부녀회장이 될테야, 17202 핸드폰 번호 궁합)

 

Dynamic programming(동적계획법)이란?

• 1950년대 Richard Bellman에 의해 개발된 알고리즘 패러다임
• 복잡한 문제를 더 간단한 하위 문제로 분해하여 단순화하는 것을 의미
• 간단한 문제의 해를 구하고, 이를 이용하여 복잡한 문제를 푼다

 

동적계획법 문제는 두 가지 특성을 가진다

 

1. 최적의 하위 구조

• 최적화 문제에 대한 솔루션이 해당 하위 문제에 대한 최적 솔루션의 조합으로 얻어낼 수 있다
• 작은 문제로 큰 문제를 해결할 때 사용되는 관계가 존재하고, 이를 함축적 순서라고 한다

 

2. 중첩되는 하위 문제

• 동적계획 알고리즘은 분할 정복 알고리즘과 구분된다
• 분할 정복 알고리즘은 해결이 어려운 문제를 분할하여 문제를 해결한다는 점에서 동적계획법과 비슷하지만 차이점이 존재한다.
• 동적계획법은 하위 문제가 중첩되고, 분할 정복 알고리즘은 하위 문제가 중첩되지 않는다

교수님 교안 참고

• 분할 정복의 예시이다
  • A는 B, C로 분할된다
  • B는 D, E로 분할되고/ C는 F, G로 분할된다
  • D+E로 B를 구하고/ F+G로 C를 구한다
  • B+C로 A를 구한다
• 동적계획법의 예시이다
  • 작은문제 D, E, F, G를 구한다
  • 큰 문제인 B를 구할 때 D+E+F를 사용하고, C를 구할 때 E+F+G를 사용
  • 더 큰 문제인 A를 구할 때 B+C를 사용한다
• 분할정복은 문제를 쪼개서 푼다면, 동적계획법은 작은문제들을 모아 큰 문제를 해결하는 느낌으로 보면 되겠다

 

동적계획법이 사용되는 예시

• 피보나치 수열
• 최단경로 문제
  • 다익스트라
  • Bellman-Ford 알고리즘
  • Floyd-Warshall 알고리즘

 

동적계획법 풀이법

• 큰 문제를 작은문제로 나눈다
• 다음 문제를 풀 때 미리 구해둔 작은 문제의 해답을 이용한다

 

 

2748 피보나치 수 2 - 브론즈1

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

2748번: 피보나치 수 2

• 작은문제들을 구해 큰 문제를 구한다
• Fn을 구하는 작은 문제는 Fn-1, Fn-2 이다
• 차근차근 하나씩 구하면 될 것 같다

 

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

    long fn2 = 0;
    long fn1 = 1;

    int cnt = 1;
    while (cnt < N) {
      long fn = fn1+fn2;
      fn2 = fn1;
      fn1 = fn;
      cnt++;
    }

    System.out.println(fn1);
  }
}

• 차근차근 하나씩 구하면 어렵지 않은 문제다
• 자료형을 long으로 안했다가 틀렸다 ㅠ

 

 

 

2775 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

 

• 부녀회장이랑은 무슨 상관인지는 모르겠다 ㅋㅋㅋ (백준 문제들은 스토리가 재밌는 것 같다)
• 0층부터 a층까지 1호~b호까지 사람수를 세고, a층까지 반복하면 될 것 같다
• 그림을 그려보면 다음과 같다

• 항상 1호의 사는 사람의 수는 1명이다
• k층 n호의 사람 수는 (k-1층 n호 사람 수) + (k층 n-1호 사람 수) 이다
• 배열의 크기가 커질 필요 없이 배열 2개만 사용해도 될 것 같다

 

풀이

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

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++) {
      int floor = Integer.parseInt(br.readLine());
      int room = Integer.parseInt(br.readLine());

      int[][] arr = new int[2][room+1];
      for (int i =1; i<=room; i++)
        arr[0][i] = i;

      int low = 0; //아래층
      int curr = 1; //현재 층수

      while (true) {
        int lowIdx = low % 2;
        int currIdx = curr % 2;

        arr[currIdx][1] = 1;

        for (int i =2; i<=room; i++)
          arr[currIdx][i] = arr[lowIdx][i]+arr[currIdx][i-1];

        if (curr == floor)
          break;

        curr++;
        low++;
      }

      sb.append(arr[curr%2][room]);
      sb.append("\n");
    }
    System.out.println(sb);
  }
}

• 테스트케이스마다 층수와 호수를 받는다
• 2개의 행과 (호수+1)개의 열을 가지는 배열 arr을 만든다 (0열은 사용하지 않을 예정)
• 아래층과 현채 층을 저장할 변수를 만든다
• 현재층 1호 값을 1로 만들고, 연산을 수행한다.   
  • (curr층의 n호) = (curr층의 n-1호) + (low층의 n호) 
  • 연산을 모두 수행한 후, low와 curr을 1씩 증가시켜준다
  • 이 과정을 원하는 층수가 될 때까지 반복한다
• 배열은 두 배열을 번갈아가면서 사용할 생각이므로, 층수%2 를 인덱스로 값을 저장한다

 

 

 

 

17202 핸드폰 번호 궁합 - 브론즈1

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

17202번: 핸드폰 번호 궁합

 

• 인접한 두 수끼리 더하고 더하는 과정을 계속 반복해야할 것 같다
• 작은 문제는 바로 눈에 보인다. 더해야 할 두 값이다!

 

문제를 잘못읽어 처음엔 큐로 풀었고, 그 뒤에 배열로도 풀어봤다

 

큐 방식 풀이(별로 좋은 방법은 아닌듯)

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

    Queue<Integer> queue = new LinkedList<>();
    for (int i =0; i<8; i++) {
      queue.add(Character.getNumericValue(one.charAt(i))%10);
      queue.add(Character.getNumericValue(two.charAt(i))%10);
    }

    while (true) {
      int size = queue.size();

      if (size == 2)
        break;

      for (int i =0; i<size-1; i++) {
        int sum = queue.poll() + queue.peek();
        queue.add(sum%10);
      }

      queue.poll();
    }

    System.out.println("" + queue.poll() + "" + queue.poll());
  }
}

• 큐에다 번호를 번갈아 넣는다
• (큐사이즈 - 1) 만큼 반복한다
  • 큐에 값을 하나 빼고, 큐 가장 끝에있는 값과 더한다
  • 더한 값을 10으로 나눈 나머지를 다시 큐에 넣는다
  • 마지막엔 큐에서 값을 하나 빼준다

 

 

배열풀이

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

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

    int[] arr = new int[16];
    for (int i =0; i<8; i++) {
      arr[2*i] = Character.getNumericValue(one.charAt(i));
      arr[2*i+1] = Character.getNumericValue(two.charAt(i));
    }

    int size = arr.length-1;

    while (true) {
      for (int i =0; i<size; i++)
        arr[i] = (arr[i]+arr[i+1])%10;

      if (size == 2)
        break;

      size--;
    }

    System.out.println("" + arr[0] + "" + arr[1]);
  }
}

• 번걸아가며 16크기의 배열에 값을 저장한다
• 현재 size를 저장하며 a[i] = a[i] + a[i+1]를 반복한다
• size가 2가 되면 반복문을 끝낸다

 

큐로 푼 건 실수였는데 시간이 조금 더 적게나왔다 ㅋㅋ

 

 

 

 

 

 

 

 

 

 

 

참고

https://en.wikipedia.org/wiki/Dynamic_programming