[10주차_수요일] 내려가기

[yeahdy]

• 사이트 : 백준(BOJ)
• 문제: 내려가기
• 번호: 2096
• 레벨: 골드5

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[yeongleej]

🤔 시간복잡도 고려사항

• n <= 100,000

=> O(N)으로 풀 수 있는 방법 생각해보기 : DP

💡 풀이 아이디어

• DP로 해결
• 최대, 최소를 모두 구해야 하므로 dp배열 2개 활용
• dp[i][]= i번째 칸까지 오는 최소 비용 or 최대 비용

  예) 최대 비용
  dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + dp[i][0]
  dp[i][1] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + dp[i][1]
  dp[i][2] = max(dp[i-1][1], dp[i-1][2]) + dp[i][2]

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 100,000 → 10^5이므로 O(N logN) 이하
• 완전 탐색은 불가능함 → DP

💡 풀이 아이디어

• 가능한 범위 내에서 현재 값으로 다음 값 결정해주기

  int[] maxDp = new int[3];
  int[] minDp = new int[3];
  // ============================
  int[] next = { 값1, 값2, 값3 };
  int[] nextMaxDp = new int[3];
  int[] nextMinDp = new int[3];
  
  nextMaxDp[0] = next[0] + Math.max(maxDp[0], maxDp[1]);
  nextMaxDp[1] = next[1] + Math.max(Math.max(maxDp[0], maxDp[1]), maxDp[2]);
  nextMaxDp[2] = next[2] + Math.max(maxDp[1], maxDp[2]);
  
  nextMinDp[0] = next[0] + Math.min(minDp[0], minDp[1]);
  nextMinDp[1] = next[1] + Math.min(Math.min(minDp[0], minDp[1]), minDp[2]);
  nextMinDp[2] = next[2] + Math.min(minDp[1], minDp[2]);
  
  maxDp = nextMaxDp;
  minDp = nextMinDp;

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 100,000
• 10^5, O(NlogN)이하

💡 풀이 아이디어

• DP이용

  dpMx[1][0] = Math.max(dpMx[0][0], dpMx[0][1]) + a;
  dpMx[1][1] = Math.max(dpMx[0][0], Math.max(dpMx[0][1], dpMx[0][2])) + b;
  dpMx[1][2] = Math.max(dpMx[0][1], dpMx[0][2]) + c;

  • 문제 조건에 따라 점화식 구성
  • dpMx[2][3]
    • 0행: dp의 이전값 저장
    • 1행: 업데이트 된 dp값 저장
    • 최소, 최대값 구한 후 이전값(0행) 업데이트

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= N <= 100,000
• 0 <= 원소 값 <= 9
• N에 대해서 이중 반복문을 사용하면 시간초과 발생

💡 풀이 아이디어

• DP 사용: map에 대한 각 행들을 입력받으면서 동시에 max와 min을 만들어나감
• int[][] max: 이차원 배열에서 각 위치마다 최댓값을 저장하는 변수

• int[][] min: 이차원 배열에서 각 위치마다 최솟값을 저장하는 변수 (0행을 제외한 나머지 행 INF 값으로 초기화)

  for(int r = 1; r < map.length; r++) {
  st= new StringTokenizer(br.readLine());
  for(int c = 0; c < 3; c++) map[r][c] = Integer.parseInt(st.nextToken());
  
  for(int pc = 0; pc < 3; pc++) {
      for(int dc = -1; dc < 2; dc++) { 
          int nc = pc + dc;
          if(nc < 0 || nc >= 3) continue;
  
          max[r][nc] = Math.max(max[r - 1][pc] + map[r][nc], max[r][nc]);
          min[r][nc] = Math.min(min[r - 1][pc] + map[r][nc], min[r][nc]);
      }
  }
  }

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: dp
• 시간복잡도: N(1 ≤ N ≤ 100,000) 숫자가 세 개씩 > O(N*3)

💡 풀이 아이디어

• 최대값 누적 배열, 최소값 누적 배열을 만들어서 이동 가능한 다음 칸에 대소 비교를 통해 메모리제이션

• Math.max(현재 누적 최대값, 이전 상태의 누적 최대값 + 현재의 숫자)

• Math.min(현재 누적 최소값, 이전 상태의 누적 최소값 + 현재의 숫자)

  //dp
  for(int i=0; i<n-1; i++){
  for(int j=0; j<LIMIT; j++){
      if(j-1 >= 0){    //왼쪽사이드
          min[i+1][j-1] = Math.min(min[i+1][j-1] , min[i][j] + board[i+1][j-1]);
          max[i+1][j-1] = Math.max(max[i+1][j-1] , max[i][j] + board[i+1][j-1]);
      }
      if(j+1 < LIMIT){ //오른쪽사이드
          min[i+1][j+1] = Math.min(min[i+1][j+1] , min[i][j] + board[i+1][j+1]);
          max[i+1][j+1] = Math.max(max[i+1][j+1] , max[i][j] + board[i+1][j+1]);
      }
      //바로아래
      min[i+1][j] = Math.min(min[i+1][j] , min[i][j] + board[i+1][j]);
      max[i+1][j] = Math.max(max[i+1][j] , max[i][j] + board[i+1][j]);
  }
  }

• 최대값: 최대값 누적 배열을 오름차순 정렬 > 마지막행의 마지막열

• 최소값: 최소값 누적 배열을 오름차순 정렬 > 마지막행의 첫번째열

[icegosimperson]

🤔 시간복잡도 고려사항

• N<= 100,000 ->O(N)
• DP[N][3]

💡 풀이 아이디어

• 경로 시작점 3개 -> 경우의 수 3가지 고려
• 내려오는 방향의 경우를 고려하여 Max, Min값 구함
• Max[], Min[]의 첫번째 행 값은 맨 처음 시작하는 숫자로 초기화

          min[i][0] = Math.min(min[i-1][0], min[i-1][1]) + dp[i][0];
          min[i][1] = Math.min(Math.min(min[i-1][0], min[i-1][1]), min[i-1][2]) + dp[i][1];
          min[i][2] = Math.min(min[i-1][1], min[i-1][2]) + dp[i][2];