[백준 JAVA] 회귀한 프로그래머의 재귀 다시풀기

 

1, 2, 3 더하기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int N, cnt;
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        for(int testcase = 1; testcase <= T; testcase++){
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            cnt = 0;

            dfs(0);

            sb.append(cnt).append("\n");
        }

        System.out.println(sb);
    }

    public static void dfs(int sum){
        if(sum == N){
            cnt++;
            return;
        }
        for(int i = 1; i <= 3; i++){
            if(sum + i > N) break;
            dfs(sum + i);
        }
    }
}

 

암호만들기

 

L, C  가 헷갈려서 시간 끔 확실히 생각필요

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int L, C;
    public static char[] code;
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new  StringTokenizer(br.readLine());

        // 1. 입력변수 받아오기
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        code = new char[C];
        st = new  StringTokenizer(br.readLine());
        for(int i = 0; i < C; i++){
            code[i] = st.nextToken().charAt(0);
        }
        Arrays.sort(code);

        // 2. 조합 재귀
        dfs(0, 0, "");

        // 4. 정답 출력
        System.out.println(sb);
    }

    public static void dfs(int at, int depth, String ans){
        // 3-1. depth에 닿고
        if(depth == L){
            // 모음이 1개 자음이 2개일경우 출력
            int gather = 0;
            int consonant = 0;
            for(int i = 0; i < L; i++){
                char a = ans.charAt(i);
                if(a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u'){
                    gather += 1;
                } else {
                    consonant += 1;
                }
            }
            if (gather >= 1 && consonant >= 2) {
                sb.append(ans).append("\n");
            }
            return;
        }

        // 3-2. 모든 알파벳 순회
        for(int i = at; i < C; i++){
            dfs(i + 1, depth + 1, ans + code[i] );
        }
    }
}

 

퇴사

 

이전에 풀었던 방법

 

import java.util.*;

public class Main {
    static int n, max = 0;
    static int[][] a;
    static int arr = 0;
    static StringBuilder sb = new StringBuilder();

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

        n = sc.nextInt();

        a = new int[2][n];

        for (int i = 0; i < n; i++) {
            a[0][i] = sc.nextInt();
            a[1][i] = sc.nextInt();
        }

        dfs(0,0);
        sb.append(max);
        System.out.println(sb);

    }

    static void dfs(int at, int cost) {
        if(at <= n) {
            if(cost>max) {
                max = cost;
            }
        } else {
            return;
        }

        for(int i = at;i < n;i ++) {
            dfs(i + a[0][i], cost + a[1][i]);

        }
    }
}

 

이번에 푼방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[][] arr;
    public static int max = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new  StringTokenizer(br.readLine());

        // 1. 입력변수 받아오기
        N = Integer.parseInt(st.nextToken());
        arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new  StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        // 2. 조합 재귀
        dfs(0, 0);

        // 4. 정답 출력
        System.out.println(max);
    }

    public static void dfs(int depth, int prise){
        if(depth == N){
            max = Math.max(max, prise);
            return;
        }
        if(depth > N){
            return;
        }

        dfs(depth+arr[depth][0], prise+arr[depth][1]);

        dfs(depth+1, prise);
    }
}

 

dp 로 푸는 법

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[][] arr;
    public static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new  StringTokenizer(br.readLine());

        // 1. 입력변수 받아오기
        N = Integer.parseInt(st.nextToken());
        arr = new int[N][2];
        dp = new int[N + 1];
        for (int i = 0; i < N; i++) {
            st = new  StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        for(int i = N - 1; i >= 0; i--){
            int take = 0;
            if(i + arr[i][0] <= N) take = arr[i][1] + dp[i + arr[i][0]];
            int skip = dp[i + 1];
            dp[i] = Math.max(take, skip);
        }

        // 4. 정답 출력
        System.out.println(dp[0]);
    }
}

 

스타트와 링크

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int N, min = Integer.MAX_VALUE;
    public static int[] arr, start, link;
    public static int[][] ability;
    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());
        ability = new int[N][N];
        arr = new int[N];
        start = new int[N/2];
        link = new int[N/2];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                ability[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 1. 팀정하기
        dfs(0,0);

        // 2. 능력치 계산

        // 팀을 반반으로 나눠야 된다

        // 3. 정답출력
        System.out.println(min);

    }
    public static void dfs(int at, int depth){
        if(depth == N / 2){
            int cnt1 = 0, cnt2 = 0;
//            for(int i = 0; i < N; i++){
//                System.out.print(i + ": " + arr[i] + " ");
//            }
            for(int i = 0; i < N; i++){
                if(arr[i] == 1){
                    start[cnt1++] = i;
                }else {
                    link[cnt2++] = i;
                }
            }
            int startS = sum(start);
            int linkS = sum(link);
            min = Math.min(min, Math.abs(startS - linkS));
            return;
        }
        for(int i = at; i < N; i++){
            arr[i] = 1;
            dfs(i + 1, depth + 1);
            arr[i] = 0;
        }
    }

    public static int sum(int[] arr){
        int sum = 0;

        for(int i = 0; i < arr.length; i++){
            for(int j = i + 1; j < arr.length; j++){
                sum = sum + ability[arr[i]][arr[j]] + ability[arr[j]][arr[i]];
            }
        }

        return sum;
    }
}

 

링크와 스타트

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static int N, min = Integer.MAX_VALUE, startN = 0, linkN = 0;
    public static int[] arr;
    public static List<Integer> start, link;
    public static int[][] ability;
    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());
        ability = new int[N][N];
        arr = new int[N];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                ability[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 1. 팀정하기 (팀 인원수 1 ~ N)
        for(int i = 1; i <= N / 2; i++){
            dfs(0, 0, i);
        }

        // 3. 정답출력
        System.out.println(min);

    }
    public static void dfs(int at, int depth, int member){
        if(depth == member){
            start = new ArrayList<>();
            link = new ArrayList<>();
            for(int i = 0; i < N; i++){
                if(arr[i] == 1) start.add(i);
                else link.add(i);
            }
            startN = calculate(start);
            linkN = calculate(link);
            min = Math.min(min, Math.abs(startN - linkN));
            return;
        }
        for(int i = at; i < N; i++){
            arr[i] = 1;
            dfs(i + 1, depth + 1, member);
            arr[i] = 0;
        }
    }
    public static int calculate(List<Integer> list){
        int sum = 0;
        for(int i = 0; i < list.size(); i++){
            int first = list.get(i);
            for(int j = i + 1; j < list.size(); j++){
                int second = list.get(j);
                sum = sum + ability[first][second] + ability[second][first];
            }
        }
        return sum;
    }
}

 

다 풀어놓고 해맷다.

1. 조합 짤때 dfs(i, depth + 1, member) => dfs(i + 1, depth + 1, member);

 

2. 계산할때 sum = sum + ability[first][second] + ability[first][second] => sum = sum + ability[first][second] + ability[second][first]

 

컴파일 에러가 안뜨는 대표적인 실수 지금 한걸 다행이라 생각해야할까? 아쉽긴하다. 오래걸리진 않았다. 풀이시간 약 30분

 

고민하는 시간이 오래걸린건 아닌데 생각보다 오래걸린거 같다. 타자치는 속도나 코드짜는 속도가 느려진거같다. 

 

근데 사실 이 방법이 좀 아닌거 같은데 왜 짜보면 또 정답인건지 의문이다. 시간 계산 해봤을때는 더 오래걸릴꺼라 생각해서 시간초과의 압박의 느꼈었다. 

 

순열은 

3. 완전 검색 - 순열

• 순열 (Permutation)
  • 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
  • 서로 다른 n개 wnd r개를 택하는 순열은 아래와 같이 표현한다.nPn = n!
  • nPr = n * (n-1) * (n-2) * … * (n-r+1)
• N개의 요소들에 대해서 n!개의 순열들이 존재한다.
  • 12! = 479,001,600
  • n > 12인 경우, 시간 복잡도 폭발적으로 상승

 💡 10! 정도만 순열로 문제 풀이를 기대 해 볼 수 있다.

 

이번 문제는 조합이긴하지만 조합보다는 그냥 부분집합으로 보는게 좋은거같다. 부분집합은 O(2^n)정도라 20까지는 괜찮다. 딱

 

gpt 의 도움을 받아 이 문제를 어떻게 풀면 시간복잡도가 더 줄어들지 물어봤더니 세가지 정도를 추천해주었다.

 

1. 0번 선수를 무조건 링크팀에 넣고 시작하기

 

2. 팀의 점수를 재귀할때마다 필요한 값만 계산해주는 방식

 

3. 최소가 0이면 더 할필요 없이 바로 빠져나오기

 

맨 처음 GPT 가 짜준코드 넣으니까 안돌아가더니 피드백 한번 후 잘돌아감

시간초도 많이 줄어듬 와 신기하네

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static int N, min = Integer.MAX_VALUE;
    public static int[] arr;
    public static int[][] ability, P;
    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());
        ability = new int[N][N];
        P = new int[N][N];
        arr = new int[N];
        arr[0] = 1;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                ability[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                P[i][j] = ability[i][j] + ability[j][i];
            }
        }

        // 1. 팀정하기 (팀 인원수 1 ~ N)
        dfs(1, 1, 0, 0);

        // 3. 정답출력
        System.out.println(min);

    }
    public static void dfs(int idx, int cntA, int scoreA, int scoreB){

        if (idx == N) {
            // 팀 A와 팀 B는 둘 다 1명이상이어야 함
            int cntB = N - cntA;
            if (cntA >= 1 && cntB >= 1) {
                int diff = Math.abs(scoreA - scoreB);
                if (diff < min) {
                    min = diff;
//                    if (min == 0) {
//                        System.out.println(0);
//                        System.exit(0);
//                    }
                }
            }
            return;
        }

        // 1) idx를 팀 A에 넣는 경우
        int addA = 0;
        // 이미 결정된 j<idx 중 팀 A에 있는 사람들과의 P만 더함 (증분 갱신)
        for (int j = 0; j < idx; j++) {
            if (arr[j] == 1) addA += P[idx][j];
        }
        arr[idx] = 1;
        dfs(idx + 1, cntA + 1, scoreA + addA, scoreB);
        arr[idx] = 0;

        // 2) idx를 팀 B에 넣는 경우
        int addB = 0;
        for (int j = 0; j < idx; j++) {
            if (arr[j] == 0) addB += P[idx][j];
        }
        // cntA 그대로
        dfs(idx + 1, cntA, scoreA, scoreB + addB);

    }
}

 

주석도 이해하기 쉽게 달아주고 변수명도 이해하기 훨씬 쉽다..

 

코테 공부를 하고 있는게 맞는건지 잘 모르겠다..ㅋㅋ 인터넷보니까 이거보다 잘 푼 버전은 없는거 같던데

 

근데 이상하게 내가 맨처음 1년전에 푼 버전도 좀 시간이 생각보단 빠르다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static int n, min = Integer.MAX_VALUE;
    public static int[] arr, arr2, visited;
    public static int[][] a;

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

        // 1. 입력값 받아오기
        n = Integer.valueOf(st.nextToken());
        a = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                a[i][j] = Integer.valueOf(st.nextToken());
            }
        }

        // 2. 팀을 나누기 위한 팀 배열 선언
        // 2-1. 인원수를 다르게 팀원을 분배해서 팀 배열 만들기
        for (int i = 1; i <= n / 2; i++) {
            arr = new int[i];
            arr2 = new int[n - i];
            visited = new int[n];
            dfs(0, 0, i);
        }

        System.out.println(min);

    }

    // 3. 팀 인원수에 따른 dfs 조합 만들기
    public static void dfs(int at, int depth, int num) {
        if (depth == num) {

            int cnt = 0;
            for(int i = 0;i<n;i++) {
                if(visited[i] == 0) {
                    arr2[cnt] = i;
                    cnt++;
                }
            }


            // 4-1. 1,2 번팀 능력치의 차이 구하기
            int sum = Math.abs(power(arr, num) - power(arr2, n-num));

            // 5. min과 비교했을때 더 작다면 min 초기화
            if(min>sum) {
                min = sum;
            }

            return;
        }

        for (int i = at; i < n; i++) {
            arr[depth] = i;
            visited[i] = 1;
            dfs(i + 1, depth + 1, num);
            visited[i] = 0;
        }

    }

    // 팀의 능력치 합 구하는 함수
    public static int power(int arr[], int num) {
        int sum = 0;

        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                sum += a[arr[i]][arr[j]];
            }
        }

        return sum;
    }
}

 

달라진 부분은 그닥없고 리스트에서 배열로 바꿨을 뿐인거같은데

 

부등호

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int k;
    public static long min = Long.MAX_VALUE, max = Long.MIN_VALUE;
    public static int[] sign, visited;
    public static String minS = "", maxS = "";
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 1. 입력값 받아오기
        k = Integer.parseInt(br.readLine());
        sign = new int[k];
        visited = new int[10];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < k; i++){
            char c = st.nextToken().charAt(0);
            if(c == '>'){
                sign[i] = 1;
            }
        }

        for(int i = 0; i < 10; i++){
            visited[i] = 1;
            dfs(1, i + "");
            visited[i] = 0;
        }

        System.out.println(maxS);
        System.out.println(minS);

    }

    public static void dfs(int depth, String result){
        if(depth == k + 1){
            if(max < Long.parseLong(result)){
                max = Long.parseLong(result);
                maxS = result;
            }

            if(min > Long.parseLong(result)){
                min = Long.parseLong(result);
                minS = result;
            }

            return;
        }

        for(int i = 0; i < 10; i++){
            if(visited[i] == 1) continue;
            if(sign[depth - 1] == 1 && result.charAt(depth - 1) - '0' > i){
                visited[i] = 1;
                dfs(depth + 1, result + i);
                visited[i] = 0;
            } else if(sign[depth - 1] == 0 && result.charAt(depth - 1) - '0' < i) {
                visited[i] = 1;
                dfs(depth + 1, result + i);
                visited[i] = 0;
            }
        }
    }

}

 

자릿수 조심 char , Integer 비교 조심