21.06.25 기록

• 백준 알고리즘 2775 풀이

  • 나의 풀이(메모리 14MB, 시간 128ms로 통과)
    

    0층인 0행의 값은 1, 2, 3, 4 … 로 1씩 증가하는 값을 가진다.
    

    모든 층의 1호실은 1의 값을 가진다.
    

    k층의 n호실의 값은 (k층 n-1호)와 (k-1층 n호)의 합과 같다.
    

    숫자가 커지는 규칙은 알았는데, 로직으로 짜려니 막막했다. 오늘도 열심히 for문을 돌려서 해결했다..!
    

  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class B2775 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringBuilder sb = new StringBuilder();
  
          int testCase = Integer.parseInt(br.readLine());
  
          for(int t = 0; t < testCase; t++) {
              int k = Integer.parseInt(br.readLine());
              int n = Integer.parseInt(br.readLine());
  
              int[][] apt = new int[k+1][n+1];
  
              //1. 모든 층의 1호실 값을 1로 저장한다.
              for(int i = 0; i <= k; i++) {
                  apt[i][1] = 1;
              }
  
              //2. 0층의 2호실 이상의 값을 각 호실의 값으로 저장한다.
              for(int j = 2; j <= n; j++) {
                  apt[0][j] = j;
              }
  
              //3. 위 1, 2에서 저장한 값을 기준으로 k층의 n호실까지 값을 저장한다.
              for(int i = 1; i <= k; i++) {
                  for(int j = 2; j <= n; j++) {
                      apt[i][j] = (apt[i-1][j] + apt[i][j-1]);
                  }
              }
  
              //4. 3에서 구한 k층의 n호실 값을 StringBuilder에 저장한다.
              sb.append(apt[k][n]).append("\n");
          }
  
          System.out.println(sb);
      }
  }
  
  

  
  

  • 해설(메모리 14.1MB, 시간 132ms로 통과)

    내 풀이는 k층의 n호실까지만 값을 구했다면, 해설은 아파트 값을 전체 생성한 후, k층의 n호실의 값만 출력했다.
    

    테스트 케이스가 많아질 수록 내 풀이 방식이 더 느려질 듯 하다.
    

  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class B2775 {
  
      public static final int[][] APT = new int[15][15];
  
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringBuilder sb = new StringBuilder();
  
          makeApt();
  
          int testCase = Integer.parseInt(br.readLine());
          for(int t = 0; t < testCase; t++) {
              int k = Integer.parseInt(br.readLine());
              int n = Integer.parseInt(br.readLine());
  
              sb.append(APT[k][n]).append("\n");
          }
  
          System.out.println(sb);
      }
  
      public static void makeApt() {
          for(int i = 0; i < 15; i++) {
              APT[i][1] = 1;
              APT[0][i] = i;
          }
  
          for(int i = 1; i < 15; i++) {
              for(int j = 2; j < 15; j++) {
                  APT[i][j] = (APT[i-1][j] + APT[i][j-1]);
              }
          }
      }
  }