📙[Algo] 24.02.20 알고리즘

알고리즘 문제) BOJ 2661. 좋은수열

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

문제 요약

• 숫자 1, 2, 3으로만 이루어지는 수열이 존재
• 나쁜 수열 : 임의의 길이의 인접한 두 개의 부분 수열이 동일할 경우
  • 123123213
  • 32121323
  • 33
• 좋은 수열 : 나쁜 수열이 아닌 수열
• 길이가 N인 좋은 수열 중 가장 작은 수 구하기

시간 제한

• 1초

입력

• N
  • 1≤N≤80

출력

• 좋을 수열 중 가장 작은 수 출력

접근법

• 각 자리마다 1~3까지만 들어올 수 있음
• 최대 80자리까지 가능
• 나쁜 수열인지 체크하기 check 함수
  • 부분 수열 크기 1
    • for i=0~N-2
      • arr[i] == arr[i+1] → X
  • 부분 수열 크기 2
    • for i =0~N-4
      • for j=0~1
        • arr[i+j] == arr[i+2+j] → X
  • 부분 수열 크기 3
    • for i=0~N-6
      • for j=0~2
        • arr[i+j] == arr[i+3+j] → X
• substring 함수 사용할 수도 있음

고민

• 답 출력하는거, 재귀 종료 조건(?) 이랑 가지치기 위치 등 하나하나 까다로웠던 문제…
• 다시 내 힘으로 풀어봐야 겠다

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] selected;
    static boolean isEnd;

    static boolean check(int cur) {

        if(cur <= 1) return true;
        int cnt;
        for (int i = 1; i <= cur / 2; i++) {
            // 부분 수열 크기 결정

            cnt = 0;
            for (int k = 0; k < i; k++) {
                // 부분수열 같은지 체크
                if (selected[cur - i * 2 + k] == selected[cur - i * 2 + i + k]) {
                    cnt++;
                }
            }

            if(cnt == i) return false;

        }

        return true;
    }

    static void recur(int cur) {
        if(!check(cur)) return;

        if (cur == N) {
            isEnd = true;
            return;
        }

        for (int i = 1; i <= 3; i++) {
            if(isEnd) return;
            selected[cur] = i;
            recur(cur + 1);
        }
    }

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

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

        selected = new int[N];
        recur(0);

        StringBuilder sb = new StringBuilder();
        for (int num : selected) {
            sb.append(num);
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1759. 암호 만들기

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

문제 요약

• 암호는 서로 다른 L개의 알파벳 소문자로 구성
  • 최소 한 개의 모음 aeiou
  • 최소 두 개의 자음
  • 암호는 알파벳이 증가하는 순서로 배열
• 암호로 사용할 법한 문자 종류는 C가지로, C개의 문자들이 주어졌을 때 가능성 있는 암호들 모두 구하기

시간 제한

• 2초

입력

• L C
  • 3≤L≤C≤15
• C개의 소문자들이 주어짐(중복X)

출력

• 줄마다 가능성 있는 암호 모두 출력

접근법

• for문이 L의 입력값에 따라 중첩 개수가 달라지므로 백트랙킹 사용
• 오름차순 형태이므로 가능한 알파벳 후보 배열을 먼저 오름차순 정렬 후 사용
• 나올수 있는 모든 암호 가짓수는 6435가지 * 가지치기(15) ⇒ 96525
• 백트랙킹 가지치기
  • 암호 조건 충족하는지 체크

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int L, C;
    static String[] chars;
    static String[] selected;
    static StringBuilder sb = new StringBuilder();

    static boolean check() {

        int cnt = 0; // 모음 개수
        for (int i = 0; i < L; i++) {
            if (selected[i].equals("a") || selected[i].equals("e") || selected[i].equals("i")
                    || selected[i].equals("o") || selected[i].equals("u")) {
                cnt++;
            }
        }

        if(cnt < 1) return false;
        if (L - cnt < 2) return false;

        return true;
    }

    static void recur(int cur, int start) {
        if (cur == L) {
            if (check()) {
                for (String aChar : selected) {
                    sb.append(aChar);
                }
                sb.append("\\n");
            }
            return;
        }

        for (int i = start; i < C; i++) {
            selected[cur] = chars[i];
            recur(cur + 1, i + 1);
        }
    }

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

        st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        chars = new String[C];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            chars[i] = st.nextToken();
        }
        Arrays.sort(chars);

        selected = new String[L];
        recur(0, 0);

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 12101. 1, 2, 3 더하기 2

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

문제 요약

• 정수 n, k가 주어졌을 때,
• n을 1,2,3의 합으로 나타내는 방법 중 k번째 오는 식 구하라

시간 제한

• 1초

입력

• N K
  • N은 11보다 작은 양수
  • k는 2^31-1보다 작거나 같은 자연수

출력

• n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력
• 없다면 -1

접근법

• 정답이 될 수 있는 숫자길이가 고정되어 있지 않기 때문에 합계로 끊어야 함
• 일단 N이 최대 11까지 가능하니까 큰 수자는 아님
• 합계가 n이 될 때를 기저조건으로 한다.
  • 즉, 1로만 채울 경우 배열 크기가 총 n까지 필요!
• 합계가 n보다 클 경우 return

코드

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

public class Main {
    static int N, K, cnt;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    static void recur(int cur, int sum) {
        if(sum > N) return;

        if (sum == N) {
            cnt++;

            if (cnt == K) {
                sb.setLength(0);
                for (int i = 0; i < cur; i++) {
                    sb.append(arr[i]);
                    if (i < cur - 1) {
                        sb.append("+");
                    }
                }
            }

            return;
        }

        for (int i = 1; i <= 3; i++) {
            arr[cur] = i;
            sum += i;
            recur(cur + 1, sum);
            arr[cur] = 0;
            sum -= i;
        }
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N];
        sb.append(-1);
        recur(0, 0);

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 14888. 연산자 끼워넣기

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

문제 요약

• N개의 수로 이루어진 수열 A1, … An
• 또한 수와 수사이에 넣을 수 있는 N-1개의 연산자가 주어짐
• 주어진 수의 순서를 바꾸지 않고, 연산자를 넣어서 수식을 만들 때, 결과 값이 최대인 것과 최소인 것 구하기
  • 연산자 우선순위 무시하고 앞에서부터 계산
  • 음수/양수는 먼저 양수로 바꾸고 몫을 취한 뒤 몫을 음수로 나눌 것

시간 제한

• 2초

입력

• 수의 개수 N
  • 2≤N≤11
• 수열 A1, … , An이 주어짐
  • 1≤Ai≤100
• 합이 N-1인 4개의 정수가 주어짐
  • 차대로 +개수, -개수, *개수, /개수

출력

• 첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력
• 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

접근법

• 일단 입력받은 기호들을 1차원 배열에 풀어서 저장하기
• 해당 배열에서 N-1개를 고르고(순열, 순서 바뀐것도 고려해야하니) 계산값들의 최대, 최소 갱신
  • 10P10으로 가능

코드

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

public class Main {
    static int N;
    static int[] arr;
    static char[] cals;
    static boolean[] visited;
    static int[] selected;
    static int max = -1000000000, min = 1000000000;

    static void recur(int cur) {
        if (cur == N - 1) {
            char sign;
            int num = arr[0];
            for (int i = 0; i < N - 1; i++) {
                sign = cals[selected[i]];
                if (sign == '+') {
                    num += arr[i + 1];
                } else if (sign == '-') {
                    num -= arr[i + 1];
                } else if (sign == '*') {
                    num *= arr[i + 1];
                } else {
                    num /= arr[i + 1];
                }
            }

            max = Math.max(num, max);
            min = Math.min(num, min);
            return;
        }

        for (int i = 0; i < N - 1; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            selected[cur] = i;
            recur(cur + 1);
            visited[i] = false;
        }
    }

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

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

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

        st = new StringTokenizer(br.readLine());
        int cnt;
        char ch;
        cals = new char[N - 1];
        for (int i = 0, j = 0; i < 4; i++) {
            cnt = Integer.parseInt(st.nextToken());
            if (i == 0) ch = '+';
            else if (i == 1) ch = '-';
            else if (i == 2) ch = '*';
            else ch = '/';

            while (cnt-- > 0) {
                cals[j++] = ch;
            }
        }

        visited = new boolean[N - 1];
        selected = new int[N - 1];
        recur(0);

        bw.write(String.valueOf(max + "\\n" + min));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 9663. N-Queen

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

문제 요약

• N*N 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 방법의 수 구하기

시간 제한

• 10초

입력

• N
  • 1≤N<15

출력

• 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수?

접근법

• 퀸은 상하좌우대각선모두 공격가능
• 내가 놓는 퀸은 내가 앞서 놓았던 퀸들의 위치에 영향을 받는다.
• 상하 : 같은 열
• 좌우 : 같은 행
• 대각선 : 행과 열의 차이가 같음
• 가지치기
  • cur ≤ 0인경우는 무조건 true
  • 같은 열, 같은 행, 열행 차이가 같은 경우인지 체크하기
• 조건을 고려하지 않고 퀸을 놀 수 있는 모든 경우의 수는(N이 14인 경우)
  • 196C14 = 880530516383349192480가지..
  • 모든 경우를 체크하면 안 된다.
    • 즉, 후보를 넣을 때부터 가능한 후보만 넣게 해야함
• 체스판의 좌표는 arr[N*N][2]의 배열에 저장한다.

⇒ N*N의 배열에 좌표를 담고 진행하면 시간초과가 뜬다. 196번 연산하는 for문을 14번 중첩한다고 생각하면,,,

어차피 같은 행이면 안되므로 cur을 row값으로 하고, for문에서 배열의 원소값을 col값으로 한다. 또한 for문 안에서 미리 가지치기를 진행해서 가능한 경우만 재귀 호출하도록 구현..

코드

import java.io.*;

public class Main {
    static int N;
    static int[] selected;
    static int answer;

    static boolean check(int cur) {
        for (int i = 0; i < cur; i++) {
            if (selected[cur] == selected[i]
                    || Math.abs(cur - i) == Math.abs(selected[cur] - selected[i])) {
                return false;
            }
        }
        return true;
    }

    static void recur(int cur) {
        if (cur == N) {
            answer++;
            return;
        }

        for (int i = 0; i < N; i++) {
            selected[cur] = i;
            if (check(cur)) {
                recur(cur + 1);
            }
        }
    }

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

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

        selected = new int[N];
        recur(0);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 25602. 캔 주기

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

문제 요약

• 캔의 종류 N가지
• i번째 캔을 A[i]개 갖고 있음
• 랑이가 i번째 날 j번째 캔을 먹었다면 만족도는 R[i][j]
• 메가 i번째 날 j번째 캔을 먹었다면 만족도는 M[i][j]
• 자연수 N과 A,R,M배열이 주어졌을 때, 현재 가진 캔으로 K일동안 랑이와 메리에게 각각 하루에 하나씩 줘서 얻을 수 있는 만족도 합의 최댓값

시간 제한

• 1초

입력

• N K
  • 1≤N≤5, 1≤K≤4
• 갖고 있는 캔의 수인 A배열이 주어짐
  • 0≤A[i]≤8, 모든 캔의 수 합은 2*K개 이상
• K줄에 걸쳐 랑이의 i번째 날 j번째 캔의 선호도 R배열이 주어짐
  • 1≤R[i][j]≤100
• K줄에 걸쳐 메리의 i번째 날 j번째 캔의 선호도 M배열이 주어짐
  • 1≤M[i][j]≤100

출력

• 랑이와 메리의 만족도의 합의 최댓값

접근법

• 매일 N가지의 캔 중에서 고르고, 이걸 총 K일 동안 하기 때문에
• 랑이, 메리가 선택한 것을 담는 배열을 K*2크기로 만든다.
  • 인덱스 → 몇 번째 날인지
    • 0~k-1 ⇒ 랑이가 선택
    • k~k*2-1 ⇒ 메리가 선택
  • 배열 원소 → 선택한 캔의 번호(1~N)
• 중복순열을 통해 선택을 진행
• 선택을 완료했다면
  • 해당 배열을 이용해서 선호도의 합을 구한다.
    • ex) R[i][arr[i]] → 랑이의 i번째 날 선택한 캔의 선호도
  • 랑이와 메리의 선호도 합의 최댓값을 갱신한다.
• N이 최대 5가지, k가 최대 4일까지 가능하므로 555*5가지로 충분히 완전탐색으로 돌 수 있음.
• 앗! 캔의 수량을 고려하지 않았다!
  • 만약 캔의 수량 그 잇아으로 소모하는 경우가 있다면 그전에 가지치기 할 것

코드

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

public class Main {
    static int N, K;
    static int[] A;
    static int[][] rang;
    static int[][] meri;
    static int[] selected;
    static int[] cnt;
    static int answer = 0;

    static boolean check() {
        for (int i = 0; i < N; i++) {
            if(A[i] < cnt[i]) return false;
        }
        return true;
    }
    static void recur(int cur) {

        if(!check()) return;

        if (cur == K * 2) {
            int sum = 0;
            for (int i = 0; i < 2 * K; i++) {
                if (i <= K - 1) {
                    sum += rang[i][selected[i]];
                } else {
                    sum += meri[i % K][selected[i]];
                }
            }

            answer = Math.max(answer, sum);
            return;
        }

        for (int i = 0; i < N; i++) {
            cnt[i]++;
            selected[cur] = i;
            recur(cur + 1);
            cnt[i]--;
        }
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

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

        rang = new int[K][N];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                rang[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        meri = new int[K][N];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                meri[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        selected = new int[K * 2];
        cnt = new int[N];
        recur(0);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}