2024.03.08 ‐ 2024.03.14

홍찬의

스타트링크

🐶 문제 해결 과정

• bfs를 사용하여 탐색을 진행한다.

1. 건물에 대한 정보를 입력 받은 후 bfs 탐색을 진행
2. 시작점을 버튼 1번 누른것이라고 생각한다.
3. 올라갈 수 있거나 방문하지 않은 곳이라면 올라간다. (현재 버튼 횟수 1증가)
4. 올라갈 수 없다면 내려갈 수 있거나 방문하지 않은 곳이라면 이동 (버튼 횟수 증가)
5. 목적지까지 갈 수 있다면 시작점 버튼 1번 누른 횟수 빼서 출력
   • 목적지 갈 수 없다면 "use the stairs" 출력

💻 코드 풀이 과정

    static void bfs(int f, int s, int g, int u, int d) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = 1;     //시작점 방문함 (1번 누른것으로 간주)

        while (!queue.isEmpty()) {
            int current = queue.poll();       // 현재위치

            if (current == g) {               // 현재위치 = 가야할 곳
                System.out.println(visited[current] - 1);   //맨 처음 버튼 누른것처럼 한거 뺀다
            }

            if (current + u <= f && visited[current + u] == 0) {  // 올라갈 수 있고 방문X
                visited[current + u] = visited[current] + 1;
                queue.add(current + u);
            }

            if (current - d > 0 && visited[current - d] == 0) {   // 내려갈 수 있고 방문X
                visited[current - d] = visited[current] + 1;
                queue.add(current - d);
            }
        }

        if (visited[g] == 0)        // 스타트링크 층에 갈 수 없음
            System.out.println("use the stairs");
    }

---

퇴사

🐶 문제 해결 과정

• 범위가 크기 때문에 DP를 활용하여 해결한다.

1. 현재 날짜가 범위 N을 벗어나지 않으면

• 점화식 : dp[i + T[i]] = max(dp[i + T[i]], dp[i] + P[i])
  • DP[현재 날짜 + 상담 걸리는 시간] = max(DP[현재 날의 상담 기간을 계산했을 때 끝나는 날], DP[현재 날까지 계산된 값] + P[현재 날짜 상담 비용])

2. 해당 날짜에 일 불가능 할 때나 오늘까지 비용을 다음 dp에 저장해야함

• dp[i + 1] = max(dp[i + 1], dp[i]) -> 다음 날짜 = 현재 누적값 vs 다음 누적

💻 코드 풀이 과정

public class 퇴사 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int[] T = new int[N];       // 상담 소요 기간
        int[] P = new int[N];       //금액


        for (int i = 0; i < N; i++) {
            T[i] = sc.nextInt();
            P[i] = sc.nextInt();
        }

        int[] dp = new int[N + 1];

        for (int i = 0; i < N; i++) {

            if (i + T[i] <= N) {       // 날짜 N 범위에 벗어나지 않으면
                dp[i + T[i]] = Math.max(dp[i + T[i]], dp[i] + P[i]);
            }

            // 해당 날짜에 일 불가능 할 때 이전까지 값 넣어주기 위해
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);    // 다음 dp = 현재 누적값 vs 다음 누적값

        }
        System.out.println(dp[N]);
    }
}

---

정경원

트리의 지름

🦊 문제 해결 과정

• dfs를 사용하여 트리 노드 간 최대 길이를 구하는 문제이다.

1. 반복문을 돌면서 노드 간 최대 길이인 지름을 구한다.
2. 이때, 노드 하나의 탐색이 끝날 때마다 방문 배열을 초기화한다.

🐥 코드 풀이 과정

        //2번 풀이 과정
        for (int i = 1; i <= n; i++) {
            visit = new boolean[n + 1];
            visit[i] = true;
            dfs(i, 0);
        }

        //1번 풀이 과정 - 트리의 지름을 구하기 위한 dfs 함수
        for (Node next : lists[current]) {
            if (!visit[next.node]) {
                visit[next.node] = true;
                dfs(next.node, radius + next.weight);
            }
            max = Math.max(radius, max);
        }

---

삼각달팽이

🦊 문제 해결 과정

• 배열에 값을 위에서부터 아래 순서로 채워 넣는 구현 문제이다.

1. n x n 크기의 2차원 배열은 만든 후에 x,y 인덱스를 조건에 따라 증감시켜준다.
2. 0이 저장되기 전까지 값을 다시 1차원 배열에 순서대로 저장한다.

🐥 코드 풀이 과정

        //1번 풀이 과정
        int[] answer = new int[(n * (n + 1)) / 2];

        int[][] arr = new int[n][n];

        int x = -1;
        int y = 0;
        int count = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {

                if (i % 3 == 0) {
                    x += 1;
                } else if (i % 3 == 1) {
                    y += 1;
                }
                else{
                    x -= 1;
                    y -= 1;
                }
                arr[x][y] = count++;
            }
        }

        //2번 풀이 과정 (dfs 함수)
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == 0) {
                    break;
                }
                answer[idx++] = arr[i][j];
            }
        }

---

쉬운 계단 수

🦊 문제 해결 과정

• dp를 활용한 문제이다.

1. 자릿(계단)수와 숫자를 담을 2차원 배열을 선언한다. 이때, 수가 커질 수 있기 때문에 long 자료 형을 사용한다.
2. 자릿수에 따라서 조건을 다르게 하여 배열을 채운다.

• 이때, 값이 커질 수 있기 때문에 지정한 상수로 나눈 값을 배열에 저장한다.
  • 조건 1: 1자리 수의 계단은 무조건 1개
  • 조건 2: 0이 들어간 계단은 1인 경우의 계단 수만 비교할 수 있다.
  • 조건 3: 9가 들어간 계단은 8인 경우의 계단 수만 비교할 수 있다.

3. 해당 길이에 해당하는 계단 수를 구한다.

🐥 코드 풀이 과정

        //1번 풀이 과정
        long[][] dp = new long[n + 1][10];

        for (int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }

        //2번 풀이 과정 (dfs 함수)
        for (int i = 2; i < n + 1; i++) {
            for (int j = 0; j < 10; j++) {

                if (j == 0) {
                    dp[i][0] = dp[i - 1][1] % V; //0일때는 1인 경우의 계단 수만
                } else if (j == 9) {
                    dp[i][9] = dp[i - 1][8] % V; //9일때는 8인 경우의 계단 수만
                } else {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % V;
                }
            }
        }

        //3번 풀이 과정
        for (int i = 0; i < 10; i++) {
            sum += dp[n][i] % V;
        }

---