📙[Algo] 24.08.29 알고리즘

알고리즘 문제) BOJ 3258. 컴포트

• 링크 : https://www.acmicpc.net/problem/3258

문제 요약

• 1에서 게임을 시작해서, Z번째 필드에 도착하는 것이 이 게임의 목표
• 도착점은 K만큼씩 시계방향으로 이동해 도달해야 한다
• 도착점으로 가는 길에 장애물이 있는 필드를 밟아서는 안 된다
• 예를들어 N=13, K=3 그리고 Z=9라고 했을 때 아람이는 1,4,7,10,13,3,6 그리고 9 의 필드를 지나게 된다
• 게임판의 정보가 주어졌을 때 도착점에 도착할 수 있는 가장 작은 K를 찾는 프로그램을 작성

시간 제한

• 1초

입력

• 첫째 줄에는 N(2 ≤ N ≤ 1000), Z(2 ≤ Z), M(0 ≤ M ≤ N-2)
  • N은 필드의 수이고 Z는 도착해야하는 필드의 번호를 의미
• 다음 줄에 M개의 서로 다른 정수
  • 정수는 장애물이 있는 필드의 번호
  • 1번과 Z번째 필드에는 장애물이 놓이지 않는다

출력

• 출력의 첫 번째 줄에 위에서 정의되어진 K를 출력

접근법

• K 1부터 N-1까지 완전 탐색으로 돌려보면서
  • 가장 먼저 Z에 도착한 K를 출력했다.
  • 이때, 한번 방문한 곳을 또 방문하게 되면 그 뒤에 수행되는 케이스도 동일하므로 한 번 방문한 필드는 방문처리했다. ⇒ 무한 루프 방지
  • 또한, 장애물에 걸린 경우에는 가능하지 않은 K므로 break를 걸었다
  • 만약 장애물에 걸리지 않고 Z에 도착했다면, 해당 K를 정답으로 출력하게끔 했다.

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 필드 개수
        int Z = Integer.parseInt(st.nextToken()); // 도착점
        int M = Integer.parseInt(st.nextToken()); // 장애물 개수

        boolean[] isObs = new boolean[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            isObs[Integer.parseInt(st.nextToken())] = true;
        }

        int cur;
        int ans = -1;
        boolean[] visited = new boolean[N + 1];
        for (int k = 1; k < N; k++) {
            cur = 1;
            Arrays.fill(visited, false);
            while (true) {
                cur += k;
                if (cur > N) cur -= N;

                // 방문한 곳 또 방문하면 끝내버리기
                if (visited[cur]) break;
                // 장애물에 걸리면 끝내버리기
                if (isObs[cur]) break;
                if (cur == Z) {
                    ans = k;
                    break;
                }
                visited[cur] = true;
            }

            if (ans != -1) break;
        }

        System.out.println(ans);
    }
}

 

알고리즘 문제) BOJ 12038.Polynesiaglot (Small2)

• 링크 : https://www.acmicpc.net/problem/12038

문제 요약

• 모든 단어는 문자로 구성(자음 또는 모음)
• 단어의 자음은 반드시 모음이 뒤따를 것
  • ex) ah는 유효 X
• C개의 다른 자음과 V개의 다른 모음이 있다면 길이가 L인 유효한 단어는 총 몇 개일까?
  • 결과값은 1000000007로 나눈 나머지로 출력

시간 제한

• 5초

입력

• 테스트 케이스의 수 T
  • 1 ≤ T ≤ 100
• 각 테스트케이스 별로 정수 C V L
  • 1 ≤ C ≤ 50
  • 1 ≤ V ≤ 50
  • 1 ≤ L ≤ 15

출력

• 각 테스트 케이스에 대해, "Case #x: y" 형식으로 한 줄에 하나의 결과를 출력
  • 테스트케이스 번호 x는 1부터 시작
  • y는 유효한 단어 개수
    • 결과값은 1000000007로 나눈 나머지로 출력

접근법

• 재귀 dp로 접근
• 현재 형성한 단어의 길이를 나타내는 cur과 이전에 자음 사용여부를 나타내는 flag변수 사용
  • 만약 flag가 1이라면 이전에 자음을 썼다는 의미므로
    • 유효한 단어가 되기 위해 무조건 모음만 붙인다
    • 만약, 이미 단어의 끝에 도달한 경우에는 뒤에 모음을 붙일 수 없어 유효한 단어가 아니므로 0 return
• L이 최대 15까지 가능하고, 각각 모음은 최대 50, 자음도 최대 50개 가능하다
  • 따라서, 재귀 함수를 수행하게 되면 모든 케이스를 볼 때 최대 100^15를 보게 되므로 dp배열에 메모이제이션을 수행
  • dp[cur][flag] : 현재 길이가 cur이고 이전에 자음 사용 여부에 따른 유효 단어의 수를 저장

코드

import java.io.*;
import java.util.*;

public class Main {
    static int C, V, L;
    static final int MOD = 1_000_000_007;
    static int[][] dp = new int[16][2];

    static int recur(int cur, int flag) {

        if (cur == L) {
            if (flag == 0) return 1;
            else return 0;
        }

        if (dp[cur][flag] != -1) return dp[cur][flag];

        int ret = 0;
        if (flag == 1) {
            for (int i = 1; i <= V; i++) {
                // 이전에 자음 사용 했다면 -> 반드시 모음 사용
                ret = (ret + recur(cur + 1, 0) % MOD) % MOD;
            }
        } else {
            for (int i = 1; i <= V; i++) {
                // 모음 사용
                ret = (ret + recur(cur + 1, 0) % MOD) % MOD;
            }
            for (int i = 1; i <= C; i++) {
                // 자음 사용
                ret = (ret + recur(cur + 1, 1) % MOD) % MOD;
            }
        }

        dp[cur][flag] = ret;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        int ret;
        for (int tc = 1; tc <= T; tc++) {
            sb.append("Case #").append(tc).append(": ");
            st = new StringTokenizer(br.readLine());
            C = Integer.parseInt(st.nextToken());
            V = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken());
            for (int[] d : dp) {
                Arrays.fill(d, -1);
            }
            ret = recur(0, 0);
            sb.append(ret).append("\\n");
        }
        System.out.println(sb);
    }
}

 

알고리즘 문제) BOJ 11482.Conversation Log 

• 링크 : https://www.acmicpc.net/problem/11482

문제 요약

• 모든 사용자가 사용한 단어들을 한 줄에 하나씩 출력

시간 제한

• 2초

입력

• 첫 번째 줄에는 메시지의 수를 나타내는 정수 M이 주어집니다. (1 ≤ M ≤ 10⁴)
• 다음 M개의 줄에는 각각 사용자의 이름(20자 이내의 소문자)과 해당 사용자가 보낸 메시지가 모두 소문자로 주어집니다
  • 공백을 포함한 전체 메시지의 총 문자는 2 × 10⁶자를 넘지 않습니다

출력

• 포럼에서 모든 사용자가 사용한 단어들을 한 줄에 하나씩 출력
  • 가장 많이 사용한 순서대로 → 같다면 글자순 내림차순
• 만약 그런 단어가 없다면 ALL CLEAR 출력

접근법

• 우선 사람의 수(메시지에 적힌 이름에서 중복을 제거한 개수)는 Set 활용하기
• “사람 + 사용단어” 조합도 Set에 담아야함 ⇒ 사람마다 처음 사용하는 건지 아닌지 판단하기 위해
• 각 단어별 등장 개수 및 사용한 사람 개수 기록 필요 ⇒ Map<단어, new 객체(단어, 등장 개수, 사용 사람 개수)>
• 출력
  • 우선순위 큐 사용했음
  • 단어의 사용 사람 개수가 Set의 크기와 같은 경우
    • 해당 단어의 등장 개수 및 단어 사전순으로 하나씩 출력

코드

import java.io.*;
import java.util.*;

public class Main {

    static class Word implements Comparable<Word> {
        String str;
        int totalUse;
        int personUse;

        Word(String str, int totalUse, int personUse) {
            this.str = str;
            this.totalUse = totalUse;
            this.personUse = personUse;
        }

        @Override
        public int compareTo(Word o) {
            if (this.totalUse == o.totalUse) return this.str.compareTo(o.str);
            else return o.totalUse - this.totalUse;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        // 이름 담을 set
        Set<String> nameSet = new TreeSet<>();
        // 이른 단어조합 담을 set
        Set<String> use = new HashSet<>();
        // 메시지 정보 담을 map
        Map<String, Word> msgMap = new TreeMap<>();

        String input, name;
        String[] arr;
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            arr = input.split(" ");
            name = arr[0];
            // 이름 set에 담기
            nameSet.add(name);
            for (int j = 1, len = arr.length; j < len; j++) {
                if (msgMap.containsKey(arr[j])) {
                    // 만약 이미 map에 해당 단어가 존재한다면
                    if (use.contains(name+" "+arr[j])) {
                        // 같은 사용자가 또 사용하는 경우
                        msgMap.replace(arr[j], new Word(arr[j], msgMap.get(arr[j]).totalUse + 1, msgMap.get(arr[j]).personUse));
                    } else {
                        // 새로운 사용자가 사용하는 경우
                        msgMap.replace(arr[j], new Word(arr[j], msgMap.get(arr[j]).totalUse + 1, msgMap.get(arr[j]).personUse + 1));
                        // "이름 단어" 형태로 set에 담기
                        use.add(name + " " + arr[j]);
                    }
                } else {
		                // 처음 보는 담어라면 map에 담기
                    msgMap.put(arr[j], new Word(arr[j], 1, 1));
                }
            }
        }

        PriorityQueue<Word> pq = new PriorityQueue<>();
        int totalUse, personUse;
        for (String key : msgMap.keySet()) {
            totalUse = msgMap.get(key).totalUse;
            personUse = msgMap.get(key).personUse;
            if (personUse >= nameSet.size()) {
                // 모든 사람이 사용했다면
                pq.offer(new Word(key, totalUse, personUse));
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            sb.append(pq.poll().str).append("\\n");
        }

        if (!sb.isEmpty()) System.out.println(sb);
        else System.out.println("ALL CLEAR");
    }
}

 

알고리즘 문제) BOJ 11727.2×n 타일링 2

• 링크 : https://www.acmicpc.net/problem/11727

문제 요약

• 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성

시간 제한

• 1초

입력

• 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

• 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력

접근법

• 재귀 dp로 접근
• cur은 현재까지 설치된 가로길이를 나타낸다.
• 타일은 총 3가지가 존재하므로 ⇒ 1 * 2 , 2 * 1 , 2 * 2
  • 각각의 타일을 설치할 때마다 cur 변수는 다음과 같이 변한다.
  • 1 * 2 , 2 * 2 ⇒ cur + 2
  • 2 * 1 ⇒ cur + 1
• 모든 케이스를 보게되면 총 3^1000가지를 보게 되므로, dp배열을 통해 메모이제이션으로 최적화를 진행했다
  • dp[cur] ⇒ 현재 가로 길이가 cur일 때의 설치 가능한 경우의수를 저장

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static final int MOD = 10_007;
    static int[] dp = new int[1001];

    static int recur(int cur) {
        if (cur > N) return 0;
        if (cur == N) return 1;

        if (dp[cur] != -1) return dp[cur];

        int ret = 0;
        // 1*2타일링으로 채우기
        ret = (ret + recur(cur + 2) % MOD) % MOD;
        // 2*1타일링으로 채우기
        ret = (ret + recur(cur + 1) % MOD) % MOD;
        // 2*2타일링으로 채우기
        ret = (ret + recur(cur + 2) % MOD) % MOD;

        dp[cur] = ret;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        Arrays.fill(dp, -1);
        System.out.println(recur(0));
    }
}