내일배움캠프 58일차 TIL _ 13주 1일차

 

• 오늘 있었던 일
  
  • 스프링 공부
  • 알고리즘

알고리즘 문제 풀기

     ● 가장 큰 수

● 가장 큰 수 //링크

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int[] visited = new int[y + 1];
        Arrays.fill(visited, Integer.MAX_VALUE);
        visited[x] = 0;


        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);

        while (!queue.isEmpty()) {
            int current = queue.poll();

            
            if (current == y) {
                return visited[current];
            }

            
            int[] nextValues = new int[]{current + n, current * 2, current * 3};

            for (int next : nextValues) {
                if (next <= y && visited[next] > visited[current] + 1) {
                    visited[next] = visited[current] + 1;
                    queue.add(next);
                }
            }
        }
        return -1;
    }
}

• • 한번에 통과했다.
  • 우선너비 탐색(BFS)를 사용해 풀었다. 이건 몇번을 해도 잘 이해가 안된다.
• 밑은 다른 사람의 풀이

• import java.util.*;
  
  class Solution {
  
      int[] dp = new int[3000003];
      int INF = 1000002;
  
      public int solution(int x, int y, int n) {
          int answer = 0;
          Arrays.fill(dp, INF);
          dp[x] = -1;
          dp[y] = 0;
          for(int num = Math.max(y - n, Math.max(y / 2, y / 3)); num >= x; num--){
              dp[num] = Math.min(dp[num + n] + 1, Math.min(dp[num * 2] + 1, dp[num * 3] + 1));
          }
          return dp[x] >= INF ? -1 : dp[x];
      }
  }

• 단순하게 풀었는데 되네?

 

---

당일 회고

• 더위를 먹것 같다. 머리가 어지럽다.