Baekjoon 3687 성냥깨비 - DP

3687번: 성냥개비

네이버 공채 코딩테스트를 마치고 더 수련하기 위해 풀어본 문제이다.

1️⃣ GetMaxNumber()

n이 홀수이면 첫 자리가 7이고 모두 1

n이 짝수이면 모두 1이다.

static String GetMaxNumber(int leftCount) {
    String result = "";
    if (leftCount == 2) {
      return "1";
    } else if (leftCount == 3) {
      return "7";
    }
    if (leftCount % 2 == 0) { // 짝수
      while (leftCount != 0) {
        result += "1";
        leftCount -= 2;
      }
    } else {
      result += "7";
      leftCount -= 3;
      while (leftCount > 0) {
        result += "1";
        leftCount -= 2;
      }
    }
    return result;
  }

2️⃣ GetMinNumber() 처음 접근 코드

남은 n이 0이 될 때까지 루프를 돌려준다.

숫자마다 필요한 성냥깨비 개수가 다르다.

남은 n이 어떤 수의 필요한 성냥깨비 개수와 같아지면 0이 아닌 그 수를 넣어준다.

static String GetMinNumber(int leftCount) {
        String result = "";
        switch (leftCount) {
            case 2:
                return "1";
            case 3:
                return "7";
            case 4:
                return "4";
            case 5:
                return "2";
            case 6:
                return "6";
            case 7:
                return "8";
            default:
                result += "1";
                leftCount -= 2;
                break;
        }
        while (leftCount > 0) {
            switch (leftCount) {
                case 2:
                    result += "1";
                    leftCount -= 2;
                    break;
                case 3:
                    result += "7";
                    leftCount -= 3;
                    break;
                case 4:
                    result += "4";
                    leftCount -= 4;
                    break;
                case 5:
                    result += "2";
                    leftCount -= 5;
                    break;
                case 6:
                    result += "0";
                    leftCount -= 6;
                    break;
                case 7:
                    result += "8";
                    leftCount -= 7;
                    break;
                default:
                    result += "0";
                    leftCount -= 6;
                    break;
            }
        }
        return result;
    }

⛔ 반례

0이 아닌 8이 필요한 성냥깨비 개수가 많으므로 이건 틀린 접근!

GetMinNumber() : DP로 풀어야해 ❗

private static void GetMinNumber() {
    min[2] = 1;
    min[3] = 7;
    min[4] = 4;
    min[5] = 2;
    min[6] = 6; // 다른 숫자 뒤에 올 때는 0
    min[7] = 8;
    min[8] = 10;
    String[] add = { "1", "7", "4", "2", "0", "8" };

    for (int i = 9; i <= SIZE; i++) {
      for (int j = 2; j <= 7; j++) {
        String curr = String.valueOf(min[i - j]) + add[j - 2];
        min[i] = Math.min(min[i], Long.parseLong(curr));
      }
    }
  }

성냥깨비 모두 넣어봄으로써 값을 비교해준다.

주의사항 ❗

Math.min을 사용하므로 min 배열을 Long.MAX_VALUE로 초기화해줘야 한다.

INT.MAX_VALUE로 하게되면 오버플로우가 발생하므로 꼭 Long.MAX_VALUE를 사용하자!

for (int i = 0; i <= SIZE; i++) {
    min[i] = Long.MAX_VALUE;
}

전체 코드

/**
 * @틀린이유 잘못된 접근 방법
 */
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    P3687();
  }

  static final int SIZE = 100;
  static int[] matches = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
  static long[] min = new long[SIZE + 1];

  static void P3687() throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
    for (int i = 0; i <= SIZE; i++) {
      min[i] = Long.MAX_VALUE;
    }
    GetMinNumber();
    for (int testcase = 0; testcase < T; testcase++) {
      int n = Integer.parseInt(br.readLine()); // 성냥개비의 개수
      String maxNumber = GetMaxNumber(n);
      System.out.println(min[n] + " " + maxNumber);
    }
  }

  static String GetMaxNumber(int leftCount) {
    String result = "";
    if (leftCount == 2) {
      return "1";
    } else if (leftCount == 3) {
      return "7";
    }
    if (leftCount % 2 == 0) { // 짝수
      while (leftCount != 0) {
        result += "1";
        leftCount -= 2;
      }
    } else {
      result += "7";
      leftCount -= 3;
      while (leftCount > 0) {
        result += "1";
        leftCount -= 2;
      }
    }
    return result;
  }

  private static void GetMinNumber() {
    min[2] = 1;
    min[3] = 7;
    min[4] = 4;
    min[5] = 2;
    min[6] = 6; // 다른 숫자 뒤에 올 때는 0
    min[7] = 8;
    min[8] = 10;
    String[] add = { "1", "7", "4", "2", "0", "8" };

    for (int i = 9; i <= SIZE; i++) {
      for (int j = 2; j <= 7; j++) {
        String curr = String.valueOf(min[i - j]) + add[j - 2];
        min[i] = Math.min(min[i], Long.parseLong(curr));
      }
    }
  }
}