알고리즘 재활 11일차 - 백준 9461, 5525, 1389번

 

34도가 무슨 말;

 

슬 코테 대비하듯 랜덤으로 문제를 뽑아 난이도랑, 문제 유형을 끄고 풀어보자.. 호호

 

파도반 수열

 

규칙적으로 반복되고, 이전의 수를 활용하는 경우기에 DP가 떠올랐다.

숫자의 규칙을 찾아 점화식을 작성해 주었다.

1	2	3	4	5	6	7	8	9	10	11	12
1	1	1	2	2	3	4	5	7	9	12	16

 

4번째부터 1번과 3번의 변을 더해 한 변이 완성이 되었고,

5번째는 4번의 변을 활용해 삼각형이 그려졌다. 

6번부터는 1번과 5번의 변을 활용해 그려졌고, 

이후 인덱스는 이 규칙이 반복되는 특징이 있었다.

점화식  Dp[i] = Dp[i-1] + Dp[i-5]

 

100까지 진행되면 오버플로우가 발생하므로, Long으로 선언해 주었다.

 

import java.io.*;
import java.util.*;
 
public class Main {// S3 파도반 수열
    public static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        N = Integer.parseInt(st.nextToken());
 
        long[] arr = new long[N];
        for (int k = 0; k < N; k++) {
            arr[k] = Integer.parseInt(br.readLine());
        }
 
        long maxNum = Arrays.stream(arr).max().getAsLong();
        long[] dp = new long[(int)Math.max(maxNum, 6) + 1];
        // 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 48 ...
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        dp[4] = 2;
        dp[5] = 2;
        dp[6] = 3;
        // 1,3 / 4 / 5,1 / 6,2 / 7,3 / 8,4/ 9,5/
        // 10, 6 짝궁 / 11이랑 7이랑 짝궁 / 12이랑 8이랑 짝궁 /
 
        for (int i = 7; i <= maxNum; i++) {
            dp[i] = dp[i - 1] + dp[i - 5];
        }
 
        for (long i : arr) {
            sb.append(dp[(int)i]).append("\n");
        }
 
        System.out.println(sb);
    }
}
 

---

IOIOI

 

 

제일 싫어하는 유형인 문자열 처리 문제였다.

IOI 이후에 N이 증가할수록 OI가 뒤에 더 붙어 N == 2인 경우 IOI + OI로 되는데

주어지는 S 문자열에 N에 해당하는 문자열 Pn이 몇 번 나오는지 판단하는 문제다.

 

IOIOIOIOIOIOI 가 S고, N이 2이라면

IOIOIOIOIOIOI 1번

IOIOIOIOIOIOI 2번

IOIOIOIOIOIOI 3번

IOIOIOIOIOIOI 4번

IOIOIOIOIOIOI 5번으로 5를 출력하면 된다.

 

이런 식으로 예제를 꾸려 보게 되면 규칙이 보이게 되는데,

I이후 OI가 N만큼 반복되는지 확인하면 우리가 찾는 Pn인지 판단할 수 있다.

따라서 I가 들어온다면 Boolean으로 체크하고 이후에 OI가 들어온다면 임의의 변수 cnt 를 늘려주었다.

cnt가 N과 같다면 Pn과 같은 문자열이므로 정답 변수인 answer을 늘려주었다.

 

import java.io.*;
import java.util.*;
 
public class Main {// S1 IOIOI
    public static int N;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        char[] S = br.readLine().toCharArray();
 
        int result = 0;
        int count = 0;
        boolean chk = false;
 
        for (int i = 0; i < M - 1; i++) {
            if (S[i] == 'I') {
                chk = true;
                count = 0;
                while (chk && i < M - 1) {
                    if (S[i + 1] == 'O' && i + 2 < M && S[i + 2] == 'I') {
                        count++;
                        if (count == N) {
                            result++;
                            count--;
                        }
                        i += 2;
                    } else {
                        chk = false;
                    }
                }
            }
        }
 
        System.out.println(result);
    }
}

---

케빈 베이컨의 6단계 법칙

 

 

A B C D 가 있을때 A가 B와 친구고, C D 는 B의 친구라면

A의 베이컨 점수는 B = 1, C,D = 2점으로 5점이된다.

결국 이는 친구들과의 관계 depth를 계산하는 문제이다.

 

2차원 Boolean 배열로 직접적인 친구인지 입력을 받아주었다.

이후 BFS 탐색을 통해 visited 배열로 중복적으로 친구를 체크하지 않게 해주었다.

큐 사이클이 돌수록 depth는 1씩 증가하며, 큐에 새로운 친구를 넣게된다면 depth + 1 만큼 더해준다.

모든 친구와의 depth를 더해주면 해당 인물의 베이컨 점수가 나오게된다.

 

마지막에 조건으로 베이컨 수가 가장 적은사람을 출력하되,

여러명이면 번호가 가장 작은 사람을 출력하기 위해 sorting 해주었다.

물론 이러한 로직 처리를 작은 넘버부터 실행하면 정렬할 필요는 없었을것 같다.

모든 데이터를 가지고 가자~ 하는 습관때문에 따로 User class로 관리했다.

 

import java.io.*;
import java.util.*;
 
public class Main {// S1 케빈 베이컨의 6단계 법칙
    public static int N, M;
    public static boolean[][] friend;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        friend = new boolean[N + 1][N + 1];
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            friend[a][b] = true;
            friend[b][a] = true;
        }
 
        User[] baconScore = new User[N + 1];
 
        for (int i = 1; i <= N; i++) {
            User user = new User(0, i);
            boolean[] visited = new boolean[N + 1];
            Queue<int[]> q = new ArrayDeque<>();
            q.add(new int[]{i, 0});
            visited[i] = true;
 
            while (!q.isEmpty()) {
                int[] current = q.poll();
                int now = current[0];
                int depth = current[1];
 
                for (int j = 1; j <= N; j++) {
                    if (friend[now][j] && !visited[j]) {
                        visited[j] = true;
                        q.add(new int[]{j, depth + 1});
                        user.bacon += depth + 1;
                    }
                }
            }
            baconScore[i] = user;
        }
        
        // 정렬 오버라이드
        Arrays.sort(baconScore, 1, N + 1, (o1, o2) -> {
            if (o1.bacon == o2.bacon) {
                return o1.num - o2.num;
            }
            return o1.bacon - o2.bacon;
        });
 
        System.out.println(baconScore[1].num);
    }
 
    public static class User {
        int bacon;
        int num;
 
        public User(int bacon, int num) {
            this.bacon = bacon;
            this.num = num;
        }
    }
}