https://softeer.ai/practice/6250

문제 소개 및 재정의

각 대회별로 점수를 정렬해두고. 모든 대회, 모든 참가자에 대해서 아래 작업을 해준다. c 대회의 i참가자의 점수를 key값으로 lowerBound나 upperBound의 index를 구하면 된다.

문제 패턴

정렬 => 이진탐색 정렬 => 맵핑

어떻게 풀까? - 캐싱

포인트

정렬한 배열을 순회하면서 값을 선택하자. 선택한 값이 이전에 선택한 값마다 달라질때마다, 다시 말해서 바뀔때마다 현재 값(key)과 현재 인덱스(value)를 매핑한다. 0번 인덱스의 값은 static하게 초기화해두자.

코드

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

// System.out.println();


public class Main {
    // 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();

    // 세팅

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        int N = Integer.parseInt(input.readLine());
        // 배열 세팅
        int[][] originalArr = new int[4][N];
        int[][] sortedArr = new int[4][N];
        Arrays.fill(sortedArr[3], 0);

        // 배열 초기화
        for(int round=0; round<3; round++){
            tokens = new StringTokenizer(input.readLine());
            for(int i=0; i < N; i++){
                int score = Integer.parseInt(tokens.nextToken());
                originalArr[round][i] += score;
                originalArr[3][i] += score;

                sortedArr[round][i] = score;
                sortedArr[3][i] += score;    
            }
        }
        // 세팅
        //// 정렬용 배열 정렬
        for(int i=0; i < 4; i++){
            Arrays.sort(sortedArr[i]);
        }
        // 작업

        // Map 채우기.
        Map<Integer, Integer> [] score_rankMapArr = new HashMap[4];
        for(int r=0; r < 4; r++){
            score_rankMapArr[r] = new HashMap();
        }

        for(int r=0; r < 4; r++){
            int coin = sortedArr[r][0];
            for(int i=0; i < N; i++){
                if(coin != sortedArr[r][i]){
                    // score가 coin 이하인 사람의 수가 i명 있다. => score가 coin보다 높은 사람의 수는 N-i명이다. => score가 coin인 사람의 등수는 N-i+1 이다.
                    score_rankMapArr[r].put(coin, N-i+1);
                    // coin 값이 바뀌는 구간에 맞게 coin값 변경.
                    coin = sortedArr[r][i];
                }
            }
            // 맨 마지막 coin 값은 바뀔일 없으므로 if 문에 안 걸린다. 따라서 따로 작업해준다. 참고로 맨 마지막 coin 값은 1등 값이다.
            score_rankMapArr[r].put(sortedArr[r][N-1], 1);
        }

        for(int r=0; r < 4; r++){     // 각 대회별로
            for(int i=0; i < N; i++){ // 각 참가자에 대해서
                int rankKey = originalArr[r][i];
                output.append(score_rankMapArr[r].get(rankKey)).append(" ");
            }
            // 대회 끝나면 줄 바꿈
            output.append("\n");

        }
        // 출력
        System.out.println(output);
        // System.out.println(Arrays.deepToString(sortedArr));

    }

}

어떻게 풀까? - 이진탐색

포인트

내림차순으로 정렬하고 lowerBound 찾기 오름차순으로 정렬하고 upperBound 찾기

코드 - 오름차순 upperBound + while문 이진탐색

package softeer;


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


public class P_2025_0302_01_오름차순_upper_binarySearch_while {
    // 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();

    // 세팅
    static int[][] originalArr;
    static int[][] sortedArr;


    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        int N = Integer.parseInt(input.readLine());
        // 배열 세팅
        originalArr = new int[4][N];
        sortedArr = new int[4][N];
        // 배열 초기화
        for(int round=0; round < 3; round++){
            tokens = new StringTokenizer(input.readLine());
            for (int i = 0; i < N; i++) {
                int score = Integer.parseInt(tokens.nextToken());
                originalArr[round][i] += score;
                originalArr[3][i] += score;

                sortedArr[round][i] += score;
                sortedArr[3][i] += score;
            }
        }
        // 세팅

        //// 정렬용 배열 정렬
        for(int i=0; i < 4; i++){
            Arrays.sort(sortedArr[i]);
        }

        // 작업
        for(int r=0; r < 4; r++){     // 각 대회별로
            for(int i=0; i < N; i++){ // 각 참가자에 대해서
                int rankKey = originalArr[r][i];
                //int left, int right, int fineMid, final int round, final int rankKey
                int left = 0;
                int right = N-1;
                int upperBound=0;
                while(left <= right){
                    int mid = left + (right-left)/2;

                    if(sortedArr[r][mid] == rankKey){
                        upperBound = mid;
                        left = mid+1;
                    } else if (sortedArr[r][mid] > rankKey) {
                        right = mid-1;
                    } else{
                        left = mid +1;
                    }
                }
                int rank = N - (upperBound+1) +1;
                output.append(rank).append(" ");
            }
            // 대회 끝나면 줄 바꿈
            output.append("\n");

        }
        // 출력
        System.out.println(output);

    }
}

코드 - 오름차순 upperBound + 재귀적 이진탐색

package softeer;


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


public class P_2025_0302_01_오름차순_upper_binarySearch_method {
    // 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();

    // 세팅
    static int[][] originalArr;
    static int[][] sortedArr;


    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        int N = Integer.parseInt(input.readLine());
        // 배열 세팅
        originalArr = new int[4][N];
        sortedArr = new int[4][N];
        // 배열 초기화
        for(int round=0; round < 3; round++){
            tokens = new StringTokenizer(input.readLine());
            for (int i = 0; i < N; i++) {
                int score = Integer.parseInt(tokens.nextToken());
                originalArr[round][i] += score;
                originalArr[3][i] += score;

                sortedArr[round][i] += score;
                sortedArr[3][i] += score;
            }
        }
        // 세팅

        //// 정렬용 배열 정렬
        for(int i=0; i < 4; i++){
            Arrays.sort(sortedArr[i]);
        }

        // 작업
        for(int r=0; r < 4; r++){     // 각 대회별로
            for(int i=0; i < N; i++){ // 각 참가자에 대해서
                int rankKey = originalArr[r][i];
                //int left, int right, int fineMid, final int round, final int rankKey
                bs(0,N-1,0,r,rankKey);
            }
            // 대회 끝나면 줄 바꿈
            output.append("\n");

        }
        // 출력
        System.out.println(output);

    }

    // 메소드
    static void bs(int left, int right, int fineMid, final int round, final int rankKey){ //
        // 바닥조건
        if(left>right){
            // 작업
            int rank = sortedArr[round].length - (fineMid+1) +1; // 전체 - 나 이하 = 나보다 등수 높은 사람의 수
            output.append(rank).append(" ");
            return;
        }
        // 재귀파트
        int mid = left + (right-left)/2;
        if( sortedArr[round][mid] == rankKey){
            bs(mid+1, right, mid, round, rankKey); // 쓸수있는 mid값 나올때마다 fineMid 갱신해서 parameter로 넘겨주면서 관리하기.
        } else if ( sortedArr[round][mid] < rankKey ) {
            bs(mid+1, right, fineMid, round, rankKey);
        } else{
            bs(left, mid-1, fineMid, round, rankKey);
        }
    }
}

코드 - 내림차순 lowerBound + 재귀적 이진탐색

package softeer;


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.StringTokenizer;


public class P_2025_0302_01_내림차순_lower_binarySearch_method {
    // 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();

    // 세팅
    static int[][] originalArr;
    static Integer[][] sortedArr;


    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        int N = Integer.parseInt(input.readLine());
        // 배열 세팅
        originalArr = new int[4][N];
        sortedArr = new Integer[4][N];
        for (int i = 0; i < 4; i++) {
            Arrays.fill(sortedArr[i], 0);
        }
        // 배열 초기화
        for(int round=0; round < 3; round++){
            tokens = new StringTokenizer(input.readLine());
            for (int i = 0; i < N; i++) {
                int score = Integer.parseInt(tokens.nextToken());
                originalArr[round][i] += score;
                originalArr[3][i] += score;

                sortedArr[round][i] += score;
                sortedArr[3][i] += score;
            }
        }
        // 세팅

        //// 정렬용 배열 정렬
        for(int i=0; i < 4; i++){
            Arrays.sort(sortedArr[i], Collections.reverseOrder());
        }

        // 작업
        for(int r=0; r < 4; r++){     // 각 대회별로
            for(int i=0; i < N; i++){ // 각 참가자에 대해서
                int rankKey = originalArr[r][i];
                //int left, int right, int fineMid, final int round, final int rankKey
                bs(0,N-1,0,r,rankKey);
            }
            // 대회 끝나면 줄 바꿈
            output.append("\n");

        }
        // 출력
        System.out.println(output);

    }

    // 메소드
    static void bs(int left, int right, int fineMid, final int round, final int rankKey){ //
        // 바닥조건
        if(left>right){
            // 작업
            int rank = fineMid+1; // 전체 - 나 이하 = 나보다 등수 높은 사람의 수
            output.append(rank).append(" ");
            return;
        }
        // 재귀파트
        int mid = left + (right-left)/2;
        if( sortedArr[round][mid] == rankKey){
            bs(left, mid-1, mid, round, rankKey); // 쓸수있는 mid값 나올때마다 fineMid 갱신해서 parameter로 넘겨주면서 관리하기.
        } else if ( sortedArr[round][mid] < rankKey ) {
            bs(left, mid-1, fineMid, round, rankKey);
        } else{
            bs(mid+1, right, fineMid, round, rankKey);
        }
    }
}

퍼포먼스 - 오름차순 upperBound + while문 이진탐색 (제일 빠름)

[ 44.58 MB | 580 ms ]

마무리

문제를 풀며 했던 실수나 약점에 대해 정리하는게 좋을것 같다.

• IDE 없는 환경에서 풀어서 컴파일 에러나 변수명 자동완성이 없어서, 코딩 퍼포먼스가 너무 떨어진다. 휴먼에러 리스크가 커져서, 좀 더 높은 집중력이 요구된다. 이번처럼 실전같은 환경에서 연습을 더 하자.
• 궁색한 이야기지만 처음 가본 카페에서 주변이 너무 산만해서 집중력이 안 좋았다.
• 그래서 입력값의 한줄 한줄이 참가자의 성적인 줄 알았다. 다시말해서, (참가자)(대회)인줄 알았는데 사실은 (대회)(참가자)였다.
• 재귀 함수의 바닥 조건에서 return을 빼먹었다. IDE에 감사하자.
• bs()의 전체 탐색 범위를 0N-1로 해야하는데, 등수라고 잘못 생각해서 1N으로 해버렸다.
• bs()에서 탐색범위를 좁히는 방향을 결정할때, 오름차순으로 정렬했다고 착각했다. 처음풀때는 내림차순으로 정렬하는 방식으로 시도했는데...
• 내림차순으로 정렬하는게 오름차순으로 정렬하는 것보다 대략 2.X배 느리다. Collercions.reverseOrder()가 범인인것 같다.

https://www.acmicpc.net/problem/17178

문제 소개 및 재정의

<입장 기준> 입장은 티켓 번호 순서대로 이루어졌다. 주최 측은 번호표 순서대로만 통과할 수 있는 입구를 만들어 두었지만, 줄에서는 마구잡이로 사람들이 기다리고 있다. 대기 공간을 이용하여 입장이 원활히 이루어지도록 하려고 한다. 콘서트장에 사람들이 제대로 들어갈 수 있는지 확인해보자. <이동 방식> 사람들은 현재 5명씩 N 줄을 서 있고, 첫 번째 줄 맨 앞사람만 이동이 가능하다. 이 사람은 콘서트장으로 입장할 수도 있고 대기 공간에서 다시 기다릴 수도 있다. 한 줄의 사람이 다 이동했다면 그다음 줄의 사람들이 이동한다. 대기 공간에는 한 줄로만 설 수 있는 공간이 있으며, 마지막에 들어온 사람부터 나갈 수 있다. 나갈 경우 바로 입장해야 하고, 다시 줄로 돌아갈 수는 없다. <순서 기준> 티켓은 A-123과 같이 한 개의 대문자 알파벳과 '-', 1000 미만의 자연수의 조합으로 이뤄어져 있다. 만약 수가 7이라면 A-7과 같이 주어진다. 티켓의 순서는 알파벳이 빠른 티켓이 빠르며, 동일하다면 더 적은 수가 더 빠르다. 티켓 번호는 중복되게 주어지지 않는다. <예시와 실제문제.> 위의 예시를 예로 들면 다음과 같이 모든 사람들이 입장할 수 있다. 그림과는 달리 대기 공간에는 무한히 많은 사람들이 들어올 수 있다는 것에 주의하여야 한다.

문제 패턴

어떻게 풀까? - 시뮬레이션

포인트

답이 정해져 있다. 티켓을 정렬해서 정답을 만들어두고, 규칙에 맞게 최적화된 시물레이션 알고리즘을 돌려서, 정답과 다른 결과가 나오면 오답으로 처리한다. 이지선다를 반복하면서 최종까지 갔을때 정답이 나올것으로 기대된다. 스택부터 확인하는 이유 => 큐에서 확인했을때 못 넣어서 스택에 넣어버리면, 스택의 상태를 그때마다 한번 건너뛰는게 되기 때문이다.

코드

퍼포먼스

[ KB | ms ]

마무리

https://www.acmicpc.net/problem/6236

문제 소개 및 재정의

N일 동안 M번 인출할수 있다. 1번 인출할때 K원씩 인출한다. K원을 인출하고 N일 동안 매일 돈을 쓴다. 써야하는 돈은 매일 다르다. 어제 쓰고 남은 잔고가 오늘 쓸 돈 보다 많으면 인출안하고 쓸수있다. 만약 잔고가 오늘 쓸 돈보다 모자르면 남은 돈을 다시 입금하고 K원만큼 출금한다. 정확히 M번을 맞춰야한다. 그냥 마지막날에 출금회수가 M번보다 작으면 무지성으로 입금과 출금을 반복하면 된다. 왜냐면 입출금을 하는데 쿨다운타임이 없기 때문이다. 따라서 큰 의미가 없는 조건으로 보인다. 그리고 현우가 사용할수 있는 전체 돈에도 제약이 없다.

문제 패턴

어떤 조건을 만족하는 최적값 K를 구하는 문제이다. 최적값이 될수 있는 범위 안에서 이진탐색을 하며 이진탐색으로 값을 얻을때마다 해당 값이 조건을 만족하는지 확인하여 탐색방향을 결정하는 방식으로 풀수있다.

어떻게 풀까? - 이진탐색

포인트

k의 범위 정하기 최소값과 최대값을 구해야한다 최소값 i일날 써야하는 돈을 Ni라고 하자. Ni의 최대값이 탐색범위의 최소값이 되어야 한다. 3일째 써야하는 돈이 500원이라고 하자. 그날 최소 500원 이상의 돈이 있어야 하는데 꺼낼수 있는 돈이 500원보다 적다면 3일을 통과할수 없게 된다. 정확히 말하면 출금을하고 통과할수있는지 확인하는 로직을 반복해서 출금회수가 M을 넘어설때 중단하고 탐색방향을 결정해도 된다. 하지만 이것보다는 탐색범위의 최소값을 Ni의 최대값으로 사용하는게 안전해보인다. 최대값: M이 1일때를 가정하자. 한번의 출금으로 N일을 버텨야 한다. 그렇다면 최소한 매일 사용하는 돈의 합을 출금해야한다. 이 값 이상의 값은 범위로서 의미가 없다.

탐색방향 결정로직 K원을 M번 꺼내서 N일동안 돈을 낼수 있는지 파악해야 한다. N일동안 생활하는데, 출금회수가 M번 이하라면 할수있는것이다. 따라서 탐색방향을 K를 줄이는 방향으로 범위를 줄인다. N일동안 생활하는데, 출금회수가 M번 초과라면 할수없는것이다. 따라서 탐색방향을 K를 키우는 방향으로 범위를 늘린다.

코드

package study.week16;
import java.io.*;
import java.util.*;
public class BOJ_6236_용돈관리 {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    // 세팅
    static int N;
    static int M;
    static int[] origin;
    static int total;
    static int bestK=Integer.MAX_VALUE;
    static int hardDay;
    // 메소드
    static void bs(int s, int e) {
        // 바닥 조건
        if(s>e) {
            // 추가작업?
            return;
        }
        // 재귀 파트
        int mid = (s+e)/2;
        if(check(mid)) {
            bs(s,mid-1);
        } else {
            bs(mid+1,e);
        }
    }
    static boolean check(int mid) { // mid=k
        int m = 0; 
        m++;// 최초 한번은 출금해야죠.
        int balance = mid;
        for (int i = 0; i < origin.length; i++) {
            if(m>M) { // 이미 실패했으니까 그만 돌자.
                break;
            }
            int Ni = origin[i];
            if(balance-Ni>=0) {
                balance -= Ni;
            } else {
                m++; // 돈 모자르네 출금해
                balance = mid; // 남은돈 입금후 K원만큼 출금했으니, 잔고는 K원
                balance -= Ni; // i번째 필요한 돈은 그대로 사용.
            }
        }
        if(m>M) {
            return false;
        } else {
            bestK = Math.min(bestK, mid);
            return true;
        }
    }
    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());
        origin = new int[N];
        // 세팅
        for (int i = 0; i < N; i++) {
            int Ni = Integer.parseInt(input.readLine());
            origin[i] = Ni;
            total+=Ni;
            hardDay = Math.max(hardDay, Ni);
        }
        // 작업
        bs(hardDay,total);
        // 출력
        System.out.println(bestK);
    }// 메인

}

퍼포먼스

[ 20,604 KB | 204 ms ]

마무리

이진탐색 문제를 연습하기 아주 좋은 문제같다.

https://www.acmicpc.net/problem/1699

문제 소개 및 재정의

https://velog.io/@bed_is_good/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-%EB%AC%B8%EC%A0%9C%EB%B2%88%ED%98%B8-%EB%AC%B8%EC%A0%9C%EC%9D%B4%EB%A6%84-JAVA

이전의 풀이는 시간복잡도와 공간복잡도가 O(N^(3/2))이다. 근데 O(N)으로 푸는 풀이를 이해해서 글을 쓴다.

어떻게 풀까? - DP

포인트

이전 값을 참고하는 부분이 minis배열인 것에 착안했다. 메모하는 공간은 minis만 있으면 된다. minis를 최악의 상태로 초기화한다. N을 1^2의 합으로만 표현할때 항의 수가 최대가 되므로 최악의 상태가 된다. 우리가 구해야 하는 것은 항의 수가 최소가 되는 최선의 상태이므로. 앞에서부터 최선의 값들을 채워나가면 된다. 그럼 앞의 값들을 참조할때, 앞의 값들은 이미 최선의 값들이 선택된 상태이므로 최선의 상태가 유지된다.

코드

package study.week14;

import java.io.*;
import java.util.*;
public class BOJ_1699_제곱수의합2 {
    // 입력고정
    static BufferedReader input = new  BufferedReader(new InputStreamReader(System.in));
    // 세팅
    static int N;
    static ArrayList<Integer> sub = new ArrayList<>(); // N의 최대값이 10^5이므로 그보다 더 큰 제곱수를 사용할일은 없음.
    static int [] dp;
    static int [] minis;
    static int INF = Integer.MAX_VALUE;
    // 메소드
    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        N = Integer.parseInt(input.readLine());
        // 세팅
        //// N이하인 제곱수 구해서 ArrayList에 넣기
        for (int n = 0+1; n < N+1; n++) {
            int nSquare = (int) Math.pow(n, 2);
            if(nSquare <= N) {
                sub.add(nSquare);
            } else {
                break;
            }
        }
        //// dp 테이블 초기화
        dp = new int[N+1];

        // 작업
        for (int row = 0+1; row < N+1; row++) { // 0일때는 0으로 초기화해둔다. 자기자신을 더하면서 항의 개수가 1로 초기화되도록 설계.
            int mini = INF;    // 초기에 비교할 대상용.
            for (int col = 0; col < sub.size(); col++) {    // 모든 제곱수를 순회하면서 지금 목표 값에서 해당 제곱수를 뺐을때의 상태를 확인. 그때의 값들 중에서 최소값을 남겨서 저장한다.
                int referIndex = row-sub.get(col);
                if(referIndex<0) { // 참고할 인덱스가 없으면 패스
                    continue;
                }
                mini = Math.min(mini, dp[referIndex]+1);    // 최소값 비교후 갱신
            }
            dp[row] = mini;                                    // 이후 재사용 위해서. 최소값 저장.
        }


        // 출력
        System.out.println(dp[N]);


    }// 메인 종료

}

퍼포먼스

[ 12,364 KB | 140 ms ]

마무리

나름 최적화에 성공했다

https://www.acmicpc.net/problem/16935

문제 소개 및 재정의

문제를 특별하게 해석할 필요가 없는 정직한 구현 문제다.

문제 패턴

주어진 방식대로 배열을 조작하는 문제이다.

어떻게 풀까? - 시뮬레이션

포인트

각 연산을 거치기 전 후의 셀의 좌표를 비교해서 맵핑하는 공식을 확보한다. 4번 연산은 3번연산을 3번 반복하는 식으로 간접적으로 구현 가능하다. 6번 연산은 5번연산을 3번 반복하는 식으로 간접적으로 구현 가능하다.

각 셀마다 최종위치를 계산해주고 해당 위치에 값을 저장하는 방식을 선택했다. 3,4번 연산은 행과 열의 길이를 서로 뒤바꾼다. 따라서 3,4번 연산할때마다 행과 열의 길이를 뒤바꾸고, 다른 셀을 선택해서 작업할때마다 행과 열의 길이를 원래대로 초기화해줘야 한다.

코드

import java.io.*;
import java.util.*;
public class Main {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();

    // 세팅
    static int N;
    static int M;        // 원본 한셀에 대해 작업이 끝날때마다 초기화하는 용도
    static int workN;     // 작업용. 3,4 명령마다 스왑하는 용도 
    static int workM;
    static int R;
    static int[][] origin;
    static int[][] answer;
    static int[] cmds;

    // 메소드
    static void reset() {
        workN=N;
        workM=M;
    }
    static void swap() { // 3,4 번 다음에 1,2,5,6 이 오면 N,M이 바뀐다. 그냥 한바닥 돌면서 하자.
        int tempN = workN;
        workN=workM;
        workM=tempN;
    }

    static int[] cmd1(int[] xy) {
        int row = xy[0];
        int col = xy[1];

        int nrow = (workN-1)-row;
        int ncol = col;
        int[] next = {nrow,ncol};
        return next;
    }

    static int[] cmd2(int[] xy) {
        int row = xy[0];
        int col = xy[1];

        int nrow = row;
        int ncol = (workM-1)-col;
        int[] next = {nrow,ncol};
        return next;
    }

    static int[] cmd3(int[] xy) {
        int row = xy[0];
        int col = xy[1];

        int nrow = col;
        int ncol = (workN-1)-row;
        int[] next = {nrow,ncol};
        swap(); // 회전 작업 다 하고 스왑
        return next;
    }

    static int[] cmd4(int[] xy) {
        xy = cmd3(xy);
        xy = cmd3(xy);
        xy = cmd3(xy);
        return xy;
    }

    static int[] cmd5(int[] xy) { // 디버깅 포인트1. 영역 4분할 위치 잘못적음. // 디버깅 포인트2. else if 조건문에 workN과 workM을 바꿔적음.
        int row = xy[0];
        int col = xy[1];

        // 1번
        if(row<workN/2 && col<workM/2) {
            int nrow = row;
            int ncol = col+workM/2;
            int[] next = {nrow,ncol};
            return next;
        }
        // 2번
        else if(row<workN/2 && col>=workM/2) {
            int nrow = row+workN/2;
            int ncol = col;
            int[] next = {nrow,ncol};
            return next;
        }
        // 3번
        else if(row>=workN/2 && col>=workM/2) {
            int nrow = row;
            int ncol = col-workM/2;
            int[] next = {nrow,ncol};
            return next;
        }
        // 4번
        else{//if(row>=workM/2 && col<workN/2) {
            int nrow = row-workN/2;
            int ncol = col;
            int[] next = {nrow,ncol};
            return next;
        }
    }

    static int[] cmd6(int[] xy) {
        xy = cmd5(xy);
        xy = cmd5(xy);
        xy = cmd5(xy);
        return xy;
    }


    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());
        R = Integer.parseInt(tokens.nextToken());
        origin = new int[N][M];
        for (int row = 0; row < N; row++) {
            tokens = new StringTokenizer(input.readLine());
            for (int col = 0; col < M; col++) {
                origin[row][col] = Integer.parseInt(tokens.nextToken());
            }
        }
        cmds = new int[R];
        tokens = new StringTokenizer(input.readLine());
        for (int i = 0; i < R; i++) {
            cmds[i] = Integer.parseInt(tokens.nextToken());
        }
        // 세팅
        int count=0;
        for (int i = 0; i < cmds.length; i++) {
            if(cmds[i]==3 || cmds[i]==4) { // 디버깅 포인트3. || 로 묶어야되는데 실수로 &&로 묶음
                count++;
            }
        }
//        System.out.println(Arrays.toString(cmds));
//        System.out.println("count: "+count);
        if(count%2==0) {
            answer = new int[N][M];
        } else { // 홀수번 90도 회전하면 행열 길이가 서로 바뀜
            answer = new int[M][N];
        }
//        System.out.println(Arrays.deepToString(answer));
        // 작업
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < M; col++) {
                reset(); // 셀마다 리셋
                int value = origin[row][col];
                int[] xy = {row,col};
                for (int i = 0; i < cmds.length; i++) {
                    int cmd = cmds[i];
                    if(cmd==1)
                        xy=cmd1(xy);
                    if(cmd==2)
                        xy=cmd2(xy);
                    if(cmd==3)
                        xy=cmd3(xy);
                    if(cmd==4)
                        xy=cmd4(xy);
                    if(cmd==5)
                        xy=cmd5(xy);
                    if(cmd==6)
                        xy=cmd6(xy);
                }
                answer[xy[0]][xy[1]] = value; // 정답의 좌표를 구했으니 값을 저장한다.
            }
        }

        // 출력값 만들기
        for (int row = 0; row < answer.length; row++) {
            for (int col = 0; col < answer[0].length; col++) {
                output.append(answer[row][col]).append(" ");
            }
            output.append("\n");
        }
        // 출력
        System.out.println(output);
    }// 메인
}

퍼포먼스

[ 296,584 KB | 472 ms ]

마무리

4,6번을 다이렉트로 계산해도 되지만, 어차피 시간복잡도는 같으므로 빠른 풀이를 위해 재사용했다.

https://www.acmicpc.net/problem/1034

문제 소개 및 재정의

아 정형적인 문제가 아니다. 너무 어렵다. 그래서 다른 사람의 해설을 참고했다. https://kosaf04pyh.tistory.com/304 여기서 얻은 힌트는 패턴이 같은것끼리만 같은 결과로 묶을수 있다는 것이었다. 힌트를 얻은 후에는 자력으로 해결했다.

문제 패턴

정형화된 문제가 아니라 패턴은 없다.

어떻게 풀까? - 애드혹

포인트

행단위로 뜯어서 이진수로 만든다. 이진수를 십진수로 변환한다. 최대 50bit의 이진수가 나올수 있으므로 long타입을 사용한다. 변환한 십진수는 id로 사용된다.

id가 같다면 같은 패턴이다. 다시 말해서 스위치를 하나라도 작동시켰을때의 결과가 서로 같다. id가 다르다면 다른 패턴이다. 스위치를 하나라도 작동시켰을때의 결과가 서로 다르다.

어떤 id가 켜질수 있는지 확인하는 로직은 다음과 같다.

• 켜야되는 스위치의 개수(realK=>r)가 K개보다 크다. => 못킨다.
• 켜야되는 스위치의 개수(realK=>r)가 K개보다 크다. => 일단 다 킨 상태를 만들수 있다.
• 근데 K번의 기회를 모두 사용해야만함.
• k-r=s(surplus) 잉여회수로 정한다.
• s가 짝수여야지만 행의 모든 곳이 켜진다. => 킬수 있다.
• s가 홀수면 다 켜진 상태에서 꼭 한 열을 꺼야한다. => 고로 킬수 없다.

중복수가 많은것부터 가능한지 확인하고, 가능하다면 그 중복수를 제출하면된다. 근데 최대 50번만 반복하면돼서 그냥 전부다 가능한지 확인하고, 가능할때 중복수의 최대값을 관리했다.

id값을 key로 두가지 맵에 매핑한다. id의 중복개수를 세는 맵에 매핑하고. 그 id가 켜지기 위해서 몇개의 스위치를 켜야하는지도 맵에 매핑한다. key를 하나씩 꺼내보면서 킬수있는지 확인한다. 킬수있으면 그 id랑 같은 패턴의 개수를 최대값과 비교해서 갱신한다.

코드

package study.week14;

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

public class BOJ_1034_램프 {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    // 세팅
    static int N;
    static int M;
    static int K;
    static Map<Long, Integer> countMap = new HashMap<>();     // long값으로 해싱하고 같은 값이 들어오면 값 +1
    static Map<Long, Integer> turnOnMap = new HashMap<>();    // long값으로 해싱한 ID에 몇개 켜야되는지 저장하기.
    static int maxi = 0;
    // 메소드
    //// id로 변환
    static long hash(char[] cArr) {
        long sum=0;
        for (int i = 0; i < cArr.length; i++) {
            if(cArr[i]=='1')
                sum += (long) Math.pow(2, i);
        }
//        System.out.println(sum);
        return sum;
    }
    //// 키는데 필요한 스위치 개수
    static int turnOn(char[] cArr) {
        int sum=0;
        for (int i = 0; i < cArr.length; i++) {
            if(cArr[i]=='0')
                sum++; // 켜야 하는 전구의 개수.
        }
//        System.out.println(sum);
        return sum;
    }
    //// 이 id가 켜질수 있는지 체크
    static boolean isOK(int r) {
        if(r>K)         // 켜야되는 스위치를 다 못킴.
            return false;
        int s = K-r;     // 잉여 스위치 구함.
        if(s%2==0)         // 잉여가 짝수면 소멸가능. 킬수있음.
            return true;
        else            // 잉여가 홀수면 소멸 불가능. 못킴.
            return false;
    }
    // 메인
    public static void main(String[] args) throws Exception{
        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());
        for (int i = 0; i < N; i++) {
            char[] cArr = input.readLine().toCharArray();     // for문 돌리기 편하게 문자열을 char[]로 받음
            long id = hash(cArr);                            // 이진수를 십진수로 바꿔서 id 만듬. 50비트라서 long으로 받음
            int turnOn = turnOn(cArr);                        // 켜야되는 전구의 개수 => 켜야되는 스위치의 개수를 저장
            turnOnMap.put(id, turnOn);                        // id 값에 켜야되는 스위치의 개수 매핑
            if(countMap.containsKey(id)) {                    // id 값을 매핑한적 있으면, 그 값에 +1 // 연습. containsKey() 연습 // 디버깅 포인트  2. countMap.containsKey(cArr) 이따구로 적었네.
                int count = countMap.get(id);                // 디버깅 포인트  2. countMap.containsKey(cArr) 이따구로 적었네. 정신없다 정신없어.
                countMap.put(id, count+1);
            } else {                                        // id 값을 매핑한적 없으면, 1 저장.
                countMap.put(id, 1);
            }
        }
        K = Integer.parseInt(input.readLine());                // 디버깅 포인트 1. 변수 입력을 안받았음 ㅋㅋ;;

        // 세팅
        // 작업
        Set<Long> keySet = countMap.keySet();                // 연습. keySet() 연습.
//        for (long key: keySet) {
////            System.out.println(key+" : "+countMap.get(key));
//            int r = turnOnMap.get(key);
//            boolean result = isOK(r);                        // 이 패턴이 킬수있는건지 판단.
////            System.out.println(r+" : "+result);
//            if(result)                                        // 이 패턴을 킬수 있다면?
//                maxi = Math.max(maxi, countMap.get(key));    // 이 패턴의 개수를 최대값과 비교해서 갱신한다.
//        }

        Long[] keys = keySet.toArray(new Long[0]);            // 연습. 배열로 만드는 연습.
//        System.out.println(Arrays.toString(keys));
        for (int i = 0; i < keys.length; i++) {
            int r = turnOnMap.get(keys[i]);
            boolean result = isOK(r);                        // 이 패턴이 킬수있는건지 판단.
            if(result)                                        // 이 패턴을 킬수 있다면?
                maxi = Math.max(maxi, countMap.get(keys[i]));    // 이 패턴의 개수를 최대값과 비교해서 갱신한다.
        }
        // 출력
        System.out.println(maxi);

    }// 메인 종료

}

퍼포먼스

[ 11,856 KB | 68 ms ]

마무리

애드혹 어렵당. 맵의 주요 메소드를 핸들링 하는 연습이 돼서 좋았다. 실수를 줄이자.

https://www.acmicpc.net/problem/1699

문제 소개 및 재정의

https://velog.io/@bed_is_good/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-2294-%EB%8F%99%EC%A0%842-JAVA

저번에 풀이한 동전2랑 같은 문제다. N이하의 제곱수들을 동전으로 사용하고, 가격 K가 N이 된다. 따라서 코드를 제외한 나머지 것들은 동전2를 참고하면 되므로 비워두겠다.

문제 패턴

어떻게 풀까? -

포인트

코드

package study.week14;

import java.io.*;
import java.util.*;
public class BOJ_1699_제곱수의합2 {
    // 입력고정
    static BufferedReader input = new  BufferedReader(new InputStreamReader(System.in));
    // 세팅
    static int N;
    static ArrayList<Integer> sub = new ArrayList<>(); // N의 최대값이 10^5이므로 그보다 더 큰 제곱수를 사용할일은 없음.
    static int [][] dp;
    static int [] minis;
    static int INF = Integer.MAX_VALUE;
    // 메소드
    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        N = Integer.parseInt(input.readLine());
        // 세팅
        //// N이하인 제곱수 구해서 ArrayList에 넣기
        for (int n = 0+1; n < N+1; n++) {
            int nSquare = (int) Math.pow(n, 2);
            if(nSquare <= N) {
                sub.add(nSquare);
            } else {
                break;
            }
        }
        //// dp 테이블 초기화
        dp = new int[N+1][sub.size()];

        minis = new int[N+1];
        // 작업
        //// dp 테이블 채우기. dp[n][k] = 제곱수 k를 더했을때 n이 된다. 이때 더한 제곱수의 최소 개수.  = minis[n-k]+1 = n-k를 만드는데 더한 제곱수의 최소개수 +1. (n-k가 음수면 못 만드니까 INF.)
        for (int row = 0+1; row < N+1; row++) { // row는 0+1부터 시작해야 됨. 0번 행은 전부 0으로 초기화해야됨. 좀 더 의미있게 하려면 여기도 INF로 채우고. sub.get(col)의 값이 row와 일치할때 1을 초기화하는게 의미적으로 맞음.
            int mini = INF;
            for (int col = 0; col < sub.size(); col++) {
                int prev = row - sub.get(col);
                if(prev<0) {
                    dp[row][col] = INF;
                } else {
                    if(minis[prev]==INF) {
                        dp[row][col] = INF;
                    } else {
                        dp[row][col] = minis[prev]+1;
                        mini = Math.min(mini, dp[row][col]); // 행의 최소값 업데이트
                    }
                }
            } // dp테이블 행 채우기 끝. minis의 동일행 채우기 시작해야함.
            minis[row] = mini;
        }
        // 출력
        System.out.println(minis[N]);


    }// 메인 종료

}

번외 : 그리디한 풀이 (실패함)

package study.week14;

import java.io.*;
public class BOJ_1699_제곱수의합3 {
    // 입력고정
    static BufferedReader input = new  BufferedReader(new InputStreamReader(System.in));
    // 세팅
    // 메소드
    static void removeBigPart(int prevNum, int depth) {
        // 바닥 조건
        if(prevNum==0) { // 직전에 N을 완성했다는 의미.
            System.out.println(depth);
            return;
        }
        // 재귀 조건
        int temp = (int) Math.sqrt(prevNum);                 // 제곱근에서 정수부만 취함. 내림은 int로 형변환해주면서 자동으로 된다.
        int nextNum = prevNum - ((int)Math.pow(temp, 2));     // 전체 수에서 가장 큰 제곱수를 빼준다. 남은 수 또한 다른 제곱수의 합으로 표현이 가능하다. 
                                                            //남은 수는 제곱근의 소수부의 제곱값에 해당된다.
        removeBigPart(nextNum, depth+1);                     // depth는 더해준 제곱수의 개수를 의미한다. 제곱수를 하나 더해줬으므로 추가한다.
    }
    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        int N = Integer.parseInt(input.readLine());
        // 세팅
        // 작업
        removeBigPart(N, 0);
        // 출력

    }// 메인 종료

}

퍼포먼스

[ 137,720KB | 248ms ]

마무리

이 문제는 동전2 문제에 비해서 제곱수를 계산해서 동전들을 직접 만들어야 하는 작업이 더 필요하다. 그런데 동전2는 골드5 티어고, 이 문제는 실버2 티어다. 둘이 바뀌는게 맞는것 같은데... 아닌가...?

https://www.acmicpc.net/problem/21610

문제 소개 및 재정의

N X N 격자가 있다. 각 cell에는 바구니가 있고. 여기에는 물이 무한히 저장된다. A[r][c] 는 r행 c열에 있는 바구니의 물의 양이다. 격자의 맨위와 맨아래 행은 고리형태로 연결돼있다. 격자의 맨 오른쪽과 맨 왼쪽 행은 고리형태로 연결돼있다. . 처음 비바라기를 시전하면 좌하단 귀퉁이에 4개의 비구름이 생긴다. . 각 명령에는 이동방향과 이동거리가 있음. 명령의 절차는 다음과 같음. .

1. 모든 구름이 di 방향으로 si칸 이동한다. .
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다. .
3. 구름이 모두 사라진다. .
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다. !! 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다. 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다. .
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

문제 패턴

어떻게 풀까? - 시뮬레이션

포인트

구름의 이동 구현 구름을 이동시키고 작업을 한 다음에, 해당 위치의 구름을 없앤다고 생각하니까. 도착한 곳에 이미 구름이 있을때 문제가 되지 않을까란 생각이 들었다. 이동한 곳에 구름이 있을때를 대비하자. 구름을 이동 시키고 해당 자리를 방문처리하자. 기존에 있던 구름도 이동시키고 이동된 자리를 방문처리하자. 그러면 모든 구름이 이동된 곳이 방문처리가 될것이다. 방문처리가 된 곳에 비를 내리면 된다. . 보드를 두개 써야하나? 이전 구름 방문 배열과 이후 구름 방문 배열 . 방문 배열을 하나만 쓸거라면, 방문처리는 현재 round값으로 갱신하는 것으로 하자. 구름이 있는 위치를 List에 저장해두고, List를 순회하면서 해당 격자에서 이동시켜서 이동한 위치의 방문배열을 갱신하는 방법. 근데 ArrayList.clear()할때 메모리가 어떻게 되는지 모르겠네. 메모리 어딘가에 쌓여있다가 나중에 G.C.되나? 아니면 바로 메모리 반납하나?

물복사 버그 마법 구현 단순하게 적힌 그대로 구현하자.

구름의 생성 구현

• 물의 양이 2이상인지 확인.
• 직전에 구름이 사라진 칸이 아닌지 확인. => 라운드 개념 도입.
• 둘다 통과하면 구름 생성.

의식의 흐름

코드

package study.week13;

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

public class BOJ_21610_마법사상어와비바라기2 {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    // 세팅
    static int N;
    static int M;
    static int[][] origin;
    static int[][] visit;
    static int[][] cmd;
    static int round;
    static int[][] deltas = {{0,-1},{-1,-1}, {-1,0},{-1,+1}, {0,+1},{+1,+1}, {+1,0},{+1,-1}}; // deltas[cmd-1][0]
    static ArrayList<int[]> clouds = new ArrayList<>();


    // 메소드
    //// 구름의 생성
    static void make() {
        // 구름의 생성이 새로운 round의 기준임.
        round++; // 새 round 업데이트
        clouds.clear();
        // 구름 현재 위치 저장
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                if( (visit[row][col]!=round-1) && (origin[row][col]>=2) ) { // 이전 라운드에 구름이 도착한 곳이 아니고, 물이 2이상 있는 곳이라면. 구름생성
                    clouds.add(new int[]{row,col});
                    origin[row][col] -=2;
                }
            }
        }
//        debug("after make");
    }
    //// 구름의 이동 (%N 하면 되는거 아님?)
    static void move(int direction, int distance) {
        // 비내리기 먼저 다하고 그 다음에 물복사버그 써야 데이터의 일관성이 유지됨. 그게 규칙임.
        // 구름이 도착할때마다 물복사 버그 쓸때는 대각선 위치에 물이 없던곳이어도. 모든 구름이 비내리기를 다 하고 나서 물복사 버그 쓸때는 그곳에 물이 있을수도 있음. 
        for (int i = 0; i < clouds.size(); i++) {
            // 구름이 도착할 위치 계산
            int x = clouds.get(i)[0];
            int y = clouds.get(i)[1];
            int dx = deltas[direction-1][0]*distance;
            int dy = deltas[direction-1][1]*distance;
            int nx = x +dx;
            int ny = y +dy;

            // 상하좌우 연결하는 스킬 
            //// 디버깅 포인트 1. 
            //// 먼저 나머지를 구하자. nx가 아주 큰 음수일때 한번의 +N으로 정상범위에 들어올수 있도록. 
            //// 그리고 N을 더해주자. 
            //// 그리고 한번더 %N을 해주자. 이미 정상범위라면 +N하면서 정상범위 밖으로 나가니까. 
            //// 이러면 5칸 짜리에서 -100칸 뒤로 가는것도 계산가능하다.
            nx = ((nx%N)+N)%N;
            ny = ((ny%N)+N)%N;

            // 비 내리기.
            origin[nx][ny] +=1;
            // 구름 사라짐.
            //// 현재 round를 저장해서, 가장 최근에 방문한 곳임을 구분
            visit[nx][ny] = round;
        }
        // 물복사 버그
        for (int i = 0; i < clouds.size(); i++) {
            // 구름이 도착할 위치 계산
            int x = clouds.get(i)[0];
            int y = clouds.get(i)[1];
            int dx = deltas[direction-1][0]*distance;
            int dy = deltas[direction-1][1]*distance;
            int nx = x +dx;
            int ny = y +dy;
            // 상하좌우 연결하는 스킬
            nx = ((nx%N)+N)%N;
            ny = ((ny%N)+N)%N;
            // 물복사 버그 사용 시점
            int bonus = bug(nx, ny);
            origin[nx][ny] += bonus;
        }
        debug("after move");
    }
    //// 물복사 버그
    static int bug(int x, int y) {
        int sum = 0;
        for (int i = 0; i < 4; i++) {
            int diagonalIndex = i*2+1; // 기존 deltas에서 인덱스가 홀수면 대각방향인 것을 활용.
            int dx = deltas[diagonalIndex][0];
            int dy = deltas[diagonalIndex][1];
            int nx = x+dx;
            int ny = y+dy; // 디버깅 포인트 2. ny = x+dy 이따구로 적어둠.
            if( (0<=nx && nx<N) && (0<=ny && ny<N) && (origin[nx][ny]>0) ) { // 보드 안에 있는 격자이고. 격자에 물이 있을때
                sum++;
            }
        }
        return sum;
    }

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());
        origin = new int[N][N];
        visit = new int[N][N];
        cmd = new int[M][2];
        //// 격자칸 받기
        for (int row = 0; row < N; row++) {
            tokens = new StringTokenizer(input.readLine());
            for (int col = 0; col < N; col++) {
                origin[row][col] = Integer.parseInt(tokens.nextToken());
            }
        }
        //// 명령어 집합 받기
        for (int i = 0; i < M; i++) {
            tokens = new StringTokenizer(input.readLine());
            cmd[i][0] = Integer.parseInt(tokens.nextToken());
            cmd[i][1] = Integer.parseInt(tokens.nextToken());
        }
        // 세팅
        debug("first");
        //// 최초의 구름 생성.
        round++; // 구름 생성할때 round가 새로 시작됨.
        //// 디버깅 포인트 3. 최초 구름 스폰지역들을 리터럴로 그대로 넣었음. (N,1), (N,2) 이렇게. 인덱스에 맞게 -1씩 해줬어야함.
        clouds.add(new int[] {(N)-1,1-1});
        clouds.add(new int[] {(N)-1,2-1});
        clouds.add(new int[] {(N-1)-1,1-1});
        clouds.add(new int[] {(N-1)-1,2-1});

        // 작업
        //// 디버깅 포인트 4.  작업순서 헷갈림. 구름의 생성이 작업의 마무리인데, 작업의 시작이라고 착각함.  
        for (int i = 0; i < cmd.length; i++) {
            int direction = cmd[i][0];
            int distance= cmd[i][1];
            move(direction, distance);
            make();
        }
        //// 합계 계산
        int sum = 0;
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                sum += origin[row][col];
            }
        }
        // 출력
        System.out.println(sum);

    } // 메인 종료

    // 디버깅 스킬.
    //// 각 함수의 호출에 따라 상태를 관찰하고 싶을때.
    //// 해당 함수 맨 마지막에 debug 코드 삽입. 어떤 함수가 불렀는지 구분하는 문자열도 그 함수에 넣어두면. 디버깅 코드 유지보수가 편해짐.
    //// 제출할때는 debug() 내부를 주석처리하면 작동안함.
    static void debug(String funcName) {
//        for (int i = 0; i < N; i++) {
//            System.out.println(Arrays.toString(origin[i]));
//        }
//        System.out.println("========================="+funcName);
    }
}

퍼포먼스

[ 17,520KB | 144ms ]

마무리

각각의 디버깅 포인트를 주의하는 연습이 필요한것 같다. 문제를 잘 읽고. 코드를 카피&페이스트 했으면 잘 수정하고. 인덱스로 변환할때 잘 하고. 대체로 잘 하는 것들인데 가끔 실수 나는곳들이다.

잘한 포인트 deltas에서 대각방향만 잘 추출해서 쓴것. 끝과 끝을 연결하는 로직. 디버깅 함수 사용.

https://www.acmicpc.net/problem/12904

문제 소개 및 재정의

참고할 문제: 백준. 12919. A와B 2

https://velog.io/@bed_is_good/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-12919-A%EC%99%80B-2-JAVA

문제 패턴

이전에 풀었던 A와B 2와 큰 맥락은 같다. 바뀐점은 입력값의 크기와 B를 추가하는 방법이다. 이번엔 B를 뒤에 추가하고 뒤집는게 아니고. 문자열을 뒤집고나서 뒤에 추가한다. 따라서 새로 추가되는 캐릭터는 항상 문자열의 맨끝에 위치한다. 따라서 복원과정에서 맨뒤의 캐릭터를 한번만 보면 결론까지 스트레이트하게 결정된다. 경우의 수가 1개라는 뜻이다.

어떻게 풀까? - 그리디

포인트

이전 코드에서 바뀐점 위주로.

메소드 bb()

<변경 전> B가 맨 앞[0]에 있으므로 [1]~[L-1]까지를 카피해감

////B를 제거한 결과를 반환
static char[] bb(char[] start) {
    int l = start.length;
    char[] result = new char[l-1];
    for (int i = 0; i < l-1; i++) {
        result[i] = start[(l-1)-i];
    }
    return result;
}

<변경 후> B가 맨 뒤[L-1]에 있으므로 [0]~[L-2]까지를 카피해감

////B를 제거한 결과를 반환
static char[] bb(char[] start) {
    int l = start.length;
    char[] result = new char[l-1];
    for (int i = 0; i < l-1; i++) {
        result[i] = start[(l-1)-1-i];
    }
    return result;
}

메소드 recursion()의 재귀파트

<변경 전> DFS 타고 갈거라 if를 따로 둬도 됨.

// 재귀 파트
char first = start[0];
char last = start[start.length-1];
if(last=='A') {
    recursion(aa(start));
} 
if(first=='B') {
    recursion(bb(start));
}

<변경 후> last만 남기면 됨. 어라 생각해보니까 여기도 if 따로둬도 되네. start를 공유하고 있는게 아니라서 상관없네. 그래도 안전하게 if - else if로 같은 분기점으로 묶음.

// 재귀 파트
char last = start[start.length-1];
if(last=='A') {
    recursion(aa(start));
} else if(last=='B') {
    recursion(bb(start));
}

코드

package solo.d1013;

import java.io.*;
import java.util.*;
public class BOJ_12904_A와B {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    // 세팅
    static char[] S;
    static char[] T;
    static int answer;
    static boolean solve;
    // 메소드

    //// A를 제거한 결과를 반환
    static char[] aa(char[] start) {
        int l = start.length;
        char[] result = new char[l-1];
        for (int i = 0; i < l-1; i++) {
            result[i] = start[i];
        }
        return result;
    }
    ////B를 제거한 결과를 반환
    static char[] bb(char[] start) {
        int l = start.length;
        char[] result = new char[l-1];
        for (int i = 0; i < l-1; i++) {
            result[i] = start[(l-1)-1-i];
        }
        return result;
    }
    //// 재귀
    static void recursion(char[] start) {
        // 바닥 조건
        if(start.length<=S.length) {     // 여기서 끝내야 함.
            if(Arrays.equals(start, S)) { // 타겟이 되는 S와 바닥에서 만들어진 문자열이 같다면 전체 재귀 종료.
                answer = 1;                // 사실상 solve 대신 써도 됨.
                solve =true;            // 더 이상의 재귀적 확장을 막기 위함.
            }
            return;
        }

        // 문제 해결된 상태면 확장없이 종료. 앞으로 추가확장 안됨. 이미 Call된 것들만 남는데, 이것들도 똑같은 방식으로 종료됨.
        if(solve)
            return;

        // 재귀 파트
        char last = start[start.length-1];
        if(last=='A') {
            recursion(aa(start));
        } else if(last=='B') {
            recursion(bb(start));
        }
        return;
    }

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        S = input.readLine().toCharArray();
        T = input.readLine().toCharArray();
        // 세팅
        // 작업
        recursion(T);
        // 출력
        System.out.println(answer);

    } // 메인종료
}

퍼포먼스

[ 12,784KB | 76ms ]

마무리

2와 거의 비슷한 문제이다. 대신 조금 더 쉬운것 같다.

https://www.acmicpc.net/problem/12919

문제 소개 및 재정의

문자열 S와 T가 주어진다. 두 문자열은 'A', 'B'로만 이루어져있다. 문자열을 바꾸는 방법은 두가지가 있다. 뒤에 A를 추가하는것. 뒤에 B를 추가하고 거꾸로 뒤집는것. . 이때, S가 바뀌는 작업을 거듭해서 T가 될수 있는지 여부를 구하시오. . S의 길이 149 T의 길이 250

문제 패턴

패턴을 잘 모르겠다. 일단 문자열이 사용된다는 것. 따라서, char[]을 쓰든 해싱작업을 거쳐야 메모리 퍼포먼스가 나올것이다. . 최적해를 구하는 방식도 아닌것 같다. DP는 아닌것 같다. 그래프 문제도 아닌것 같다. 완전탐색을 시도해보자.

어떻게 풀까? - 완전탐색

포인트

S에서 T로 가는 모든 경우의 수를 만드는 방식으로 접근했다. 최악의 경우 S의 길이는 1, T의 길이는 50이다. 이때 49번의 문자열 확장과정이 필요하다. 한번의 확장과정에서 2 가지의 경우의수가 나온다. 따라서 2⁴⁹ 가지의 경우의 수가 나온다. 이는 10¹⁵ 와 맞먹는 수치로 퍼포먼스가 안 나온다. 알면서도 방법이 없어서 해봤다. 역시나 시간초과가 발생했다.

T에서 S로 가는 방법을 택했다. 해체는 조립의 역순이다. 조립하는 경우의 수와 해체하는 경우의 수가 다를 때가 있는것 같다. 이 문제가 그러하다. 조립할때는 항상 2가지 경우의 수가 나오지만, 해체할때는 문자열의 맨앞과 맨뒤의 캐릭터에 따라서 경우의 수가 바뀐다. 쉽게 말해서, 맨앞이 B일때만 B를 추가하는 확장이 가능했던거고. 맨 뒤가 A일때만 A를 추가하는 확장이 가능했던거다. 앞과 뒤를 경우의 수에 맞게 나눠보았다. . AA => 뒤의 A삭제 가능 AB => 아무것도 못함. 바닥 조건임 BA => 앞의 B삭제 가능, 뒤의 A삭제 가능 BB => 앞의 B삭제 가능 . T에서 S로 가는 경우 0,1,2가지의 경우의 수가 나올수 있기 때문에 일종의 가지치기 효과를 기대했다.

T를 S로 만드는 작업을 복원이라고 하자. 그렇다면 S를 T로 만드는 작업의 순서를 반대로 하면된다. A를 추가하는 로직을 복원화해서 메소드로 만들었다. B를 추가하는 로직을 복원화해서 메소드로 만들었다. 이후에는 재귀적으로 DFS 과정을 통해서 문자열을 복원했고. 목표 문자열과 동일한 길이가 됐을때, 같은 문자열인지 확인했다. . 같은 문자열인게 확인되면, 더 이상의 재귀작업(확장)을 하지 않도록 막는 로직도 추가했다.

코드

package study.week13;

import java.io.*;
import java.util.*;
public class BOJ_12919_A와B2_2 {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    // 세팅
    static char[] S;
    static char[] T;
    static int target;
    static int answer;
    static boolean solve;
    // 메소드

    //// A를 제거한 결과를 반환
    static char[] aa(char[] start) {
        int l = start.length;
        char[] result = new char[l-1];
        for (int i = 0; i < l-1; i++) {
            result[i] = start[i];
        }
        return result;
    }
    ////B를 제거한 결과를 반환
    static char[] bb(char[] start) {
        int l = start.length;
        char[] result = new char[l-1];
        for (int i = 0; i < l-1; i++) {
            result[i] = start[(l-1)-i];
        }
        return result;
    }
    //// 재귀
    static void recursion(char[] start) {
//        System.out.println(Arrays.toString(start)); // 디버깅용 코드
        // 바닥 조건
        if(start.length<=S.length) {     // 여기서 끝내야 함.
            if(Arrays.equals(start, S)) { // 타겟이 되는 S와 바닥에서 만들어진 문자열이 같다면 전체 재귀 종료.
                answer = 1;                // 사실상 solve 대신 써도 됨.
                solve =true;            // 더 이상의 재귀적 확장을 막기 위함.
            }
            return;
        }

        // 문제 해결된 상태면 확장없이 종료. 앞으로 추가확장 안됨. 이미 Call된 것들만 남는데, 이것들도 똑같은 방식으로 종료됨.
        if(solve)
            return;

        // 재귀 파트
        char first = start[0];
        char last = start[start.length-1];
        if(first=='A' && last=='A') {
            recursion(aa(start));
        } 
        else if(first=='A' && last=='B') {
                return;
        } else if(first=='B' && last=='A') {
            recursion(aa(start));
            recursion(bb(start));
        } else if(first=='B' && last=='B') {
            recursion(bb(start));
        }
        return;
    }

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        S = input.readLine().toCharArray();
        T = input.readLine().toCharArray();
        target = S.length;
        // 세팅
        // 작업
        recursion(T);
        // 출력
        System.out.println(answer);

    } // 메인종료

}

퍼포먼스

[ 11,540KB | 64ms ]

참고 후 리팩토링

package study.week13;

import java.io.*;
import java.util.*;
public class BOJ_12919_A와B2_3 {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    // 세팅
    static char[] S;
    static char[] T;
    static int answer;
    static boolean solve;
    // 메소드

    //// A를 제거한 결과를 반환
    static char[] aa(char[] start) {
        int l = start.length;
        char[] result = new char[l-1];
        for (int i = 0; i < l-1; i++) {
            result[i] = start[i];
        }
        return result;
    }
    ////B를 제거한 결과를 반환
    static char[] bb(char[] start) {
        int l = start.length;
        char[] result = new char[l-1];
        for (int i = 0; i < l-1; i++) {
            result[i] = start[(l-1)-i];
        }
        return result;
    }
    //// 재귀
    static void recursion(char[] start) {
//        System.out.println(Arrays.toString(start)); // 디버깅용 코드
        // 바닥 조건
        if(start.length<=S.length) {     // 여기서 끝내야 함.
            if(Arrays.equals(start, S)) { // 타겟이 되는 S와 바닥에서 만들어진 문자열이 같다면 전체 재귀 종료.
                answer = 1;                // 사실상 solve 대신 써도 됨.
                solve =true;            // 더 이상의 재귀적 확장을 막기 위함.
            }
            return;
        }

        // 문제 해결된 상태면 확장없이 종료. 앞으로 추가확장 안됨. 이미 Call된 것들만 남는데, 이것들도 똑같은 방식으로 종료됨.
        if(solve)
            return;

        // 재귀 파트
        char first = start[0];
        char last = start[start.length-1];
        if(last=='A') {
            recursion(aa(start));
        } 
        if(first=='B') {
            recursion(bb(start));
        }
        return;
    }

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        S = input.readLine().toCharArray();
        T = input.readLine().toCharArray();
        // 세팅
        // 작업
        recursion(T);
        // 출력
        System.out.println(answer);

    } // 메인종료

}

맨뒤가 A일때 걸고 맨앞이 B일때 걸고 if문을 따로 쓰면 else if문을 주렁주렁 쓰지 않아도 된다는것을 깨달았다. (맞힌 사람의 코드를 보고)

마무리

두가지 스킬이 중요했다.

1. 확인되면 모든 재귀를 멈추는 방법. 이제 슬슬 익숙해짐.
2. 정방향 탐색과 역방향 탐색의 경우의 수가 다를수있다. 이 사실에 익숙해지고, 바로 떠올려서 기본적으로 고려할수 있을만큼 연습하자.

https://www.acmicpc.net/problem/2294

문제 소개 및 재정의

n가지 종류의 동전이 있다. 한 종류의 동전을 중복해서 여러개 사용할수 있다. 이 동전들로 K원을 만들려고 한다. 이때 동전의 개수를 최소화하고 그 수를 구하시오. 만약, K원을 만들수 없다면 -1을 제출하시오.

문제 패턴

최적해를 구하는 문제이다. 이전 상황을 이용해서 풀수있을것 같다. 쪼갤수 없는 냅색과 비슷한 부분이 있는것 같다.

어떻게 풀까? - 완전탐색

전체 경우의 수를 어떻게 구해야 할지 감이 잘 안 온다. 다양한 가치를 가진 동전의 조합을 K로 조율하는 과정부터 로직이 너무 복잡해질것 같다.

어떻게 풀까? - DP

포인트

각 가격별로 필요한 동전의 최소개수를 저장해서 이전 상태의 값으로 사용하자. 그러면 현재 X원 짜리 동전을 내서 K값을 만들때 K-X원 상태의 값을 사용해서 손쉽게 구할수 있다.

Ki = 1원부터 K원까지의 값. 1,2,3,4,5,6,...,K AJ = 각 동전종류의 값어치. ex) 1,5,12, ..., An dp[Ki][Aj] = 마지막으로 Aj를 내서 Ki가 될때, 필요한 동전의 최소개수. dp[Ki][Aj] = dp[Ki-Aj][X]의 최소값 +1

코드

package study.week13;

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

public class BOJ_2294_동전2 {

    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;

    // 세팅
    static int N;
    static int K;
    static int[] coins;
    static int[] minis;
    static int[][] dp;
    static int INF = Integer.MAX_VALUE;
    // 메서드
    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        K = Integer.parseInt(tokens.nextToken());
        coins = new int[N];
        for (int i = 0; i < N; i++) {
            coins[i] = Integer.parseInt(input.readLine()); // 굳이 중복 없앨 필요 없음. 정렬할 필요도 없음.
        }
        // 세팅
        dp = new int[K+1][N];     // K값을 그대로 쓰기 위해서 0번 인덱스도 추가. 
                                // 이렇게 하면 장점. 0번에 0의 값을 넣어두면, 
                                // (Kj-Aj==0) 일때 DP[Ki-Aj][X]의 값이 항상 0이고 
                                // 이때 +1을 하는 전체 로직으로 초기화를 함께 수행할수 있다.
                                // 이 알고리즘은 도달불가능 표시와, 단 한번의 초기화(값을 채워나갈 기원점), 그리고 전체 로직으로 구성돼있다

        minis = new int[K+1];     // 각 가격별 최소 동전수를 저장하는 용도의 배열. 매번 dp의 행을 읽어도 되지만, 그냥 최적화 해봤음. 
                                // dp테이블에 열 하나 추가해서 거기다가 넣어도 되지만, 뭔가 직관성 떨어져서 배열로 분리해서 만듬.
        // 작업
        for (int k = 0+1; k < K+1; k++) {     // k=0일때인 dp[0][x]는 자동으로 0으로 초기화 된 상태.
            // int mini = INF;                // 행마다 추가로 저장되는 값과 mini값 비교해서 갱신하다가(그래서 당연하게도 for문 밖에서 선언.), 마지막에 최소값인 상태일때 minis에 저장하는 넣는용도.
                                            // 이렇게 하려다가. 복잡한것 같아서 직관성 위주로 코드를 전환. 행 완성했을때, 해당 행 한바퀴 돌면서 최소값 갱신해서 minis에 넣는 방식으로 전환.
            // 행 채우기.
            for (int i = 0; i < N; i++) {
                int Ai = coins[i];
                if(k-Ai<0) {
                    dp[k][i] = INF;         // 이전 상태가 -값이라면 현실에서 불가능한 상태 => 도달 불가능지점.
                } else{
                    int preValue = minis[k-Ai];
                    if(preValue==INF) {
                        dp[k][i] = preValue;
                    } else {
                        dp[k][i] = minis[k-Ai]+1;
                    }
                }
            }
            // 행의 최소값 구해서 저장하기.
            int mini = INF;
            for (int i = 0; i < N; i++) {
                int compare = dp[k][i];
                mini = Math.min(mini, compare);
            }
            minis[k] = mini;
        }
        // 출력
        if(minis[K]==INF) {
            System.out.println(-1);
        } else {
            System.out.println(minis[K]);
        }

    }// 메인 종료
}

숏코드

package study.week13;

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

public class BOJ_2294_동전2 {

    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;

    // 세팅
    static int N;
    static int K;
    static int[] coins;
    static int[] minis;
    static int[][] dp;
    static int INF = Integer.MAX_VALUE;
    // 메서드
    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        K = Integer.parseInt(tokens.nextToken());
        coins = new int[N];
        for (int i = 0; i < N; i++) {
            coins[i] = Integer.parseInt(input.readLine());
        }
        // 세팅
        dp = new int[K+1][N];
        minis = new int[K+1];
        // 작업
        for (int k = 0+1; k < K+1; k++) {     
            for (int i = 0; i < N; i++) {
                if(k-coins[i]<0 || minis[k-coins[i]] ==INF) 
                    dp[k][i] = INF;
                else
                    dp[k][i] = minis[k-coins[i]]+1;
            }
            int mini = INF;
            for (int i = 0; i < N; i++) {
                mini = Math.min(mini, dp[k][i]);
            }
            minis[k] = mini;
        }
        // 출력
        if(minis[K]==INF) 
            System.out.println(-1);
        else 
            System.out.println(minis[K]);

    }// 메인 종료
}

퍼포먼스

[ 16,464KB | 96ms ]

마무리

DP는 항상 최적의 상태를 유지한다. 연쇄적으로. 이전 상태는 최적의 상태로 유지되고. 따라서 다음 상태도 최적이 된다는 점이 포인트이다. 어떤 점 B을 구할때, 그 점이 어떤 점들(Ai)에서 와가지고 B에 모이는 것인지 생각하면 편하다. B는 어떤 Ai들로부터 오는것인지 파악하면, Ai에서 최선의 값을 골라서 B에 사용해주면 되는 것이다.

역시 숏코드는 별로다. 의미있는 변수명으로 바꿔주는 중간단계를 가져가면서 논리의 가독성을 챙기는게 좋다.

https://www.acmicpc.net/problem/1062

문제 소개 및 재정의

영어 알파벳 26개중 K개를 가르칠수 있다. 이때 읽을수 있는 단어의 개수의 최대값을 구하시오. 단어에는 "anta"와 "tica"가 필수적으로 들어간다. 단어의 개수는 50개 이하의 자연수이다. K는 0이상 26이하의 정수이다. 단어는 소문자로만 이루어져있고, 길이는 8~15이다.

K개의 알파벳을 어떤 set으로 가르쳐야 최대한 많은 단어를 읽을수 있는지 고민해야한다. 다시 말하면 위의 조건을 만족하는 최적의 조합을 구해야 한다는 말이다.

문제 패턴

문제 상황이 주어지고, 조합에 따라 해결력이 다르다고 할때. 제일 좋은 조합을 찾는 문제이다.

어떻게 풀까? - 완전탐색

포인트

26개에서 K개를 고르는 조합의 경우의 수는 ₂₆C_K 이다. 이때 조합의 최대값은 K가 13일때이다. (파스칼의 삼각형 참고) ₂₆C₁₃ 은 대략적으로 10⁷ = 천만 정도이다. 퍼포먼스상 대략 천만개의 조합은 커버 가능하다. 하나의 조합당 50개의 단어, 최대 15의 길이를 가진 단어를 검사해야하므로. 50*15=750 번의 연산이 필요하다고 예상된다. 그럼 전체 연산은 천만 X 750 = 75억 이 된다. 아, 이건 완탐으로 주어진 시간내에 안될텐데.

그래서 그런지 문제에서는 "anta"와 "tica"라는 조건을 추가한듯 하다. "anta"와 "tica"는 [a,c,i,n,t] 5개의 알파벳이 사용된다. 따라서 이 5개는 필수적으로 가지고 있어야 단어를 읽을수 있다. K가 5미만이라면 읽을수 있는 단어는 0개 5이상이라면 그때부터 조합을 만드는 방식으로 문제를 해결할수있다. 그러면 전체 알파벳 풀의 크기는 26-5=21이 되고. ₂₁C₁₁ = 대략 32만이 된다. 32만 X 750 은 75억의 3%정도 되는 수치이다. (32만이 천만의 3%정도) 75억을 33으로 나누면 대략 2억정도 된다. (32만 X 750 = 240,000,000) 이 정도면 완탐으로 퍼포먼스가 나온다.

조합이 구해지면 각 단어마다. 각 철자마다 조합에 포함돼있는지 검사한다.

• 만약에 포함되지 않았다면, 그 단어는 못 읽는거로 처리한다.
• 만약에 포함되어 있다면, 다음 철자로 넘어간다.
  단어의 끝까지 포함돼있다면 해당 조합에서 읽을수 있는 단어의 수를 +1해준다. 마지막 단어까지 검사한 후 읽을수 있는 단어의 수를 여태까지 최대값과 크기를 비교해서 갱신한다.

코드

package study.week12;

import java.io.*;
import java.util.*;
public class BOJ_1062_가르침 {

    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;

    // 세팅
    static int N;
    static int K;
    static char[][] words;
    static char[] comboK; // 재귀에서 leaf로 태워보낼 리스트. 메모리 아끼기 위함. 안 이래도 되겠는데?
    static char[] fixPool = {'a','n','t','i','c'};
    static char[] realPool = {'b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z'};

    static int countMax = 0;
    // 메소드
    //// 조합 구하기.
    static void makeCombo(int nowDigit, int targetDigit, char[] leaf, char[] pool, int start) {
        // 바닥 조건
        if(nowDigit>=targetDigit) {
            // 추가작업
//            System.out.println(Arrays.toString(leaf));
            readWords(leaf);
            return;
        }

        // 재귀 파트
        for (int i = 0+start; i < pool.length; i++) {
            leaf[nowDigit] = pool[i];
            makeCombo(nowDigit+1, targetDigit, leaf, pool, i+1);
        }
    }

    //// 단어 읽기.
    static void readWords(char[] leaf) {
        int count = 0;
        boolean can = true;
        // 단어들에서 단어순회
        for (int i = 0; i < words.length; i++) {
            char[] word = words[i];
            can = true;    // can == true면 단어를 읽을수있다. false면 못 읽는다. 
            // 단어에서 철자순회
            for (int j = 0; j < word.length; j++) {
                char c = word[j];
                if(canRead(c, leaf)==false) {
                    can = false;
                    break; // 못 읽는 글자 나옴 => 이 단어 패스 
                }
            } // 철자 순회 종료
            if(can) {
                count++; // 여기에 도착했다는 뜻은 can이 false가 되지 않았다는 뜻. 그 단어를 끝까지 읽었다는 뜻.
            }
        } // 단어 순회 종료
        countMax = Math.max(countMax, count);
    }

    //// 읽을수 있는 글자인지 확인.
    static boolean canRead(char c, char[] leaf) {
        // 고정풀에서 읽을수 있으면 트루 리턴
        for (int i = 0; i < fixPool.length; i++) {
            if(fixPool[i]==c) {
                return true;
            }
        }
        // 조합풀에서 읽을수 있으면 트루 리턴
        for (int i = 0; i < leaf.length; i++) {
            if(leaf[i]==c) {
                return true;
            }
        }
        // 여기까지 오면 못 읽는거니까 false 리턴
        return false;
    }

    // 메인
    public static void main(String[] args) throws Exception {

        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        K = Integer.parseInt(tokens.nextToken());
        words = new char[N][];
        for (int i = 0; i < N; i++) {
            words[i] = input.readLine().toCharArray();
        }
        // 세팅
        comboK = new char[K];
        // 작업
        if(K<5) {
            System.out.println(countMax);
        } else {
            K-=5; // 고정풀에서 K개중에서 5개를 이미 사용함.
            makeCombo(0, K, new char[K], realPool, 0);
            System.out.println(countMax);
        }
        // 출력

    }// 메인 종료

}

퍼포먼스

[ 13,260 KB | 592 ms ]

마무리

realPool을 리터럴로 넣지 말고, ASCII 코드를 활용해서 생성하는 메서드로 만들었으면 더 깔끔하고, 휴먼에러가 없어질것 같은 코드인것 같다.

22년 6월에 표준화가 완료된 HTTP/3.0의 기반이 되는 프로토콜로 Google에서 완성한 기술이다. 본 문서에서는 HTTP/2.0에 어떤 한계가 있었으며 그것을 극복하기 위해서 QUIC 프로토콜이 나오게 된 그 배경에 집중할 계획입니다.

QUIC 프로토콜 어쩌다가 나왔나?

HTTP/2.0의 태생적 한계 (TCP의 한계와 유사)

HTTP/2.0은 이전에 비해 많은 부분이 향상되었습니다.

하지만 TCP 기반으로 동작하기 때문에 TCP가 가진 태생적 한계를 벗어날 수가 없습니다.

TCP는 연결수립이 느리다

TCP는 신뢰성, 안정성을 중요하게 생각하는 프로토콜입니다.

데이터를 보낼때 중간에 손실되지 않고 확실하고 안전하게 전달돼야합니다.

그것을 위해서 연결하는 과정이 필요한데, 이 과정이 느립니다.

TCP는 어떻게 신뢰성을 보장하는가?

TCP가 확실하게 데이터를 주고 받기 위해서 사용하는 것이 일련번호(sequence number)입니다.

TCP에서는 데이터를 보낼 때, 여러 개의 패킷으로 나누어보냅니다.

한번에 많은 데이터를 보내는 경우 대역폭을 많이 차지할 수 있기 때문입니다.

이때, 패킷은 sequence number가 포함합니다. 이것이 중간에 손실된 데이터가 있는지 검증하는 수단이 됩니다. 이를 바탕으로 중간에 손실된 데이터 유무를 확인할수 있고 그로인해 데이터 전송의 신뢰성이 보장되는 것입니다.

예를 들어서 여러분이 책을 읽는다고 가정합시다.

책은 1~100페이지 분량이고 장르는 추리소설입니다.

여기서 책은 데이터, 페이지는 패킷에 대응됩니다.

우리는 한 페이지씩 전달받아 읽을수 있습니다.

1~10페이지 까지는 순서대로 전달받아서 밀실사건의 개요를 이제 막 알게된 참입니다.

밀실에서 어떻게 사람을 해쳤을까, 왜 그랬을까 흥미진진해지는 참입니다.

그런데 다음으로 갑자기 80페이지를 받고, 거기서 사건의 범인을 바로 알게됩니다.

느닷없는 스포일러 공격을 당한 여러분은 이후에는 꼭 받은 페이지의 번호를 확인하게 됩니다.

스포일러를 막기 위해서 10페이지를 읽은 다음엔 11페이지만 받으려는 것입니다.

받은 페이지가 11페이지가 아니라 80페이지라면 읽어보지도 않고 '11페이지 줄래?' 하고 요청합니다.

이런 방식으로 일련번호를 확인하면 빠지는 데이터가 없이 (스포일러 없이) 안전한 전달이 가능합니다.

TCP에 3-way-handshake는 왜 필요한가?

이렇게 sequence number를 사전에 확립하기 위해서 필요한 절차 = 3-way-handshake입니다.

TCP는 양방향 통신이기 때문에 클라이언트도, 서버도 데이터를 보낼 수 있습니다.

따라서 누가 보낸건지를 구분할 수 있는 수단이 있으면 좋을것 같습니다.

그 수단으로 각자의 sequence number가 좋을것 같습니다.

이때 맨처음에 생성하는 일련번호를 ISN(Initial Sequence Number)라고 합니다.

그리고 둘 다 서로의 초기 일련번호를 알 필요가 있습니다.

이것을 서로에게 알려주기 위해서 3-way-handshake가 필요한 것입니다.

여기까지 1-RTT가 소요됩니다.

(1-handShake)==========================================================
영희 -> 철수 : 철수야 내 ISN은 256란다.(SYN)

(2-handShake)==========================================================
영희 <- 철수 : 너의 ISN을 받았어. 256구나 알겠어(ACKnowledge)!
                             나는 257(256+1)을 받을 준비가 되었어(ACK)
영희 <- 철수 : 영희야 그리고 내 ISN은 567이야 (SYN)

(3-handShake)==========================================================
영희 -> 철수 : 너의 ISN을 받았어. 567이구나 알겠어(ACKnowledge)!
                             나는 568(567+1)을 받을 준비가 되었어(ACK)

여기에 더해 보안을 신경 쓴 TLS handshake가 더해지면 어떻게될까요?

TLS handshake :

TLS는 보안 통신을 위해서 설계된 프로토콜입니다.

그리고 TLS handshake란 이 TLS를 이용해서 안전한 통신을 하기 위한 과정입니다.

간략하게 설명하면, 서버와 클라이언트가 서로 호환되는 암호화 알고리즘을 선택하고, 암호화에 사용될 난수와 서버의 인증서 그리고 키를 교환하는 과정입니다.

TLS핸드쉐이크까지 마무리 된 이후부터 본격적으로 클라이언트가 서버에게 원하는 요청을 시작할 수 있습니다.

여기서 포인트는 가장 진보된 버전이 1.3 버전에서는 2-way-handShake(1-RTT) 가 소요된다는 점입니다.

[시각 자료 링크] https://www.google.com/search?sca_esv=02c44965d6d4b280&sca_upv=1&q=tls+1.3+handshake&udm=2&fbs=AEQNm0DmKhoYsBCHazhZSCWuALW8l8eUs1i3TeMYPF4tXSfZ96qP8jk59Ek0sz1u1YABeO8HG8dr9Z0pIiXpKYIhEwOJ2k8lQbNlrF2IBe5Y93_wn74_g9ge6EQ1dgjgMphf3g5MCZD_eRS1DLkW2s-y6cYET69KBvTgd_m3pzjrs6BtOVZu3aBkeAJnxFCo_jkBM5qNhKzT7uFNlTSO0hxIekHLzMo25Q&sa=X&sqi=2&ved=2ahUKEwjG4N7ww96IAxX7sFYBHXk4MoAQtKgLegQIFBAB&biw=1920&bih=930&dpr=1#vhid=SbE_ZzHAKXdvYM&vssid=mosaic

작은 결론 :

RTT는 쉽게 말해서 요청과 응답사이의 시간입니다.

RTT가 많아지면 안 좋은 이유를 이해하기 편하게하기 위해서 최악의 경우를 상정하겠습니다.

지구 반대편으로 요청을 하게되면 데이터는 지구를 한바퀴 돌아야합니다.

데이터 전달 속도는 빛의 속도이므로 RTT는 최소 133ms가 소요됩니다. (빛은 지구를 1초에 7바퀴 반 돔)

이것으로 인해 로딩 시간이 길어지면 사용자 경험이 안 좋아집니다.

따라서 사용자 경험 개선을 위해서 로딩시간을 줄이고 싶은데.

RTT시간을 줄일수는 없으므로(광속은 상수이기 때문에 ),

아예 RTT수 자체를 줄여야 한다는 쪽으로 사고가 이동한것 같습니다.

핵심은 TCP-Handshake가 진행된 다음에 TLS-Handshake 추가적으로 실행된다는 점입니다.

Handshake가 반복되면서 전체적인 RTT가 증가하게 됩니다.

이것이 TCP의 연결수립이 느린 이유입니다.

두 Handshake 패턴이 비슷한데? 한꺼번에 할수 있지 않을까요? 그러면 RTT수가 줄지 않을까요?

Q. 한꺼번에 할수 있겠다는 근거는 무엇일까요?

A. TCP-Handshake의 결과가 TLS-Handshake에서 필요하지 않기 때문입니다.

그래서 어떻게 해결했는가?

TCP-Handshake와 TLS-Handshake를 병합하는 QUIC 프로토콜을 개발하면서 해결했습니다.

왜 진작 TCP-Handshake와 TLS-Handshake를 병합하지 않았을까?

설계 구조와 호환성 그리고 라이브 서비스

TCP는 전송계층에서 동작하며 TLS는 애플리케이션 계층에서 동작합니다.

서로 다른 계층에서 상호작용을 최소화하도록 설계되었기 때문에 병합하기 위해서는 내부적으로 통합하는 프로토콜을 새로 만들어야 합니다.

그러지 않고 TCP 내부에서 통합하는 업데이트를 해버리면, 기존 TCP와 호환하던 네트워크 장비들과는 호환되지 않습니다.

해당 장비도 그에 맞는 업데이트를 한다면 가능합니다.

하지만 그러기 위해서는 기존의 네트워크 장비들의 운영체제를 업데이트 해야합니다.(TCP는 운영체제의 커널에 깊이 통합됐기 때문에).

이것은 전세계적인 단위의 인프라를 업데이트 해야하는 문제기 때문에 현실적으로 어렵습니다.

기존의 TCP로 잘 돌아가던 것들은 유지하기 위해서, 운영체제 업데이트 없이 해당 문제를 해결하려면은 애플리케이션 레벨에서의 프로토콜 구현하면 됩니다. 그렇게 만들어진게 QUIC 프로토콜입니다.

QUIC 프로토콜은 애플리케이션 계층상의 프로토콜이므로 전송계층으로 사용할 프로토콜이 필요합니다. 그럼 이때 TCP와 UDP 둘중에 무엇을 사용해야할까요? 앞서 말했듯이 TCP는 아닙니다.

왜냐하면 TCP를 사용하기 위해서는 이미 약속된 Handshake를 지워야하는 OS 업데이트가 필요합니다. 이렇게 네트워크 장비의 OS 업데이트를 시킬거면 QUIC을 따로 만들필요가 없겠죠?

UDP는 이미 약속된 Handshake가 없기 때문에 네트워크 장비의 OS 업데이트 없이 애플리케이션 레벨에서의 프로토콜로 TCP와 TLS의 기능(장점)을 구현하여 문제를 해결할수 있습니다.

왼쪽 그림을 보면 기존의 TCP위에 TLS가 독립적으로 존재합니다.

하지만 오른쪽 그림의 QUIC에서는 TLS를 내장하고 있습니다.

TCP를 사용하면 연결을 수립할때 TCP다음 TLS에게 바톤이 넘어가면서 각 단계에서 RTT가 발생합니다.

그에 반면, QUIC를 사용하는 경우에는 TLS단계를 QUIC 단계에서 함께 처리할수 있습니다.

따라서, QUIC 단계 하나에서만 RTT가 발생한다고 해석할수 있습니다

QUIC의 장점

1. 본문에서의 on Topic
   1. RTT수를 줄였다.
2. 본문에서의 off Topic
   1. TCP 레벨의 Head-of-Line Blocking 문제 해결
   2. IP 주소가 변경되어도 연결을 유지할 수 있도록 설계됨
      1. 네트워크 전환이 발생해도 연결을 다시 설정할 필요가 없기 때문에 모바일 환경에서 더 안정적인 연결을 제공함
      2. 기존 TCP는 연결이 끊기면 다시 HandShake하면서 연결시작해야함. 오래 걸림…

QUIC의 단점

대표적으로 호환성 문제가 있다.

QUIC는 새로운 프로토콜이기 때문에 아직 지원하지 않는 클라이언트나 서버가 다수 존재할것이다.

따라서 이들과는 호환되지 않는다.

사용하는 곳(HTTP/3 지원 웹 사이트)

• 구글
  • 유튜브
  • 그외 대부분의 서비스
• 클라우드 플레어
  • 클라우드 플레어를 사용하는 모든 웹 사이트에 기본적으로 적용됨.
  • 그외 메이저 CDN
• 네이버 검색
  • https://n.news.naver.com/mnews/article/119/0002658085?sid=105
• 토스 페이먼츠
  • https://blog.toss.im/article/tosspayments-upgrades-web-protocol
• 나무위키
• 페이스북
  • 인스타그램
• 넷플릭스
• ZOOM

레퍼런스: https://namu.wiki/w/HTTP/3

더 알아보기

• 0-RTT (제로-라운드 트립)

:BONUS: TCP레벨에서의 HOLB가 해결된 멀티플렉싱 :

TCP에서의 패킷 전송 흐름 :

위쪽의 주황색은 TCP에서의 패킷 전송흐름입니다. 위에서 설명드렸다시피, TCP는 신뢰성을 중요하게 생각하는 프로토콜이기 때문에 각각의 패킷들이 순서에 맞게 도착하도록 해야합니다. 그것을 위해서 byte range가 주어져있습니다. 주황색 그림을 예로 들어 설명해보겠습니다.

packet1이 도착함 → packet1의 byte range 확인 후 이전 byte range와 연속적인지 비교 → 연속적임 → 기억 →

packet3이 도착함 → packet3의 byte range 확인 후 이전 byte range와 연속적인지 비교 → 연속적이지 않음 →

packet2 재전송 요청 → packet2 응답으로 올때까지 다른 packet들은 모두 대기

packet1과 packet3이 stream1에 속하는 데이터고 packet2가 stream2에 속하는 데이터라고 가정해보겠습니다.

그렇다면 packet2가 손실된 것은 packet1과 packet3의 데이터와는 큰 상관이 없음에도 불구하고 packet3는 그냥 기다린것이 됩니다.

QUIC에서의 패킷 전송 흐름 :

그런데 QUIC은 이런 문제를 각각의 패킷에 stream id를 부여함으로써 해결합니다.

여기에선 각각의 패킷마다 그 안에 stream id를 가지고 있습니다. 이게 핵심입니다.

1번 패킷이 먼저 도착하고 그 다음에 3번 패킷이 도착했다고 가정하겠습니다.

다시 말해서 packet 2에 손실이 생긴 것입니다.

만약 TCP였다면 곧 바로 packet2를 재전송 요청했을 것입니다.

하지만, QUIC에서는 패킷이 도착한다? 그러면 stream id를 먼저 확인합니다.

그런 다음, 이전 stream id에서 가지고 있던 byte range를 확인합니다.

아래는 또 다른 예시를 더 자세하게 풀어쓴 내용입니다.

packet 1이 도착했다.stream id를 확인하니 1번 stream이다. 해당 스트림에 대한 byte range를 기억한다.

packet 3이 도착했다.stream id를 확인해보니 1번 stream이다. 그러면 이전에 받은 stream1의 byte range를 확인한다. 확인해보니 0-449다. 지금 받아온 byte range는 450-999다. byte range 사이의 어떤 gap도 존재하지 않는다. 정상이라고 처리한다.

packet 4를 받았다.stream id를 확인해보니 2번 stream이다. 그러면 이전에 stream id 2번의 byte range를 확인한다. 어, 그런데 해당 데이터가 존재하지 않는다. 지금 받아온 byte range는 300-599인데, 0-299라는 gap이 존재한다. stream id 2 번에 대한 이전 패킷을 다시 요청해야겠다. stream 2번에 해당하는 이전 패킷을 요청한다.

다시 손실된 패킷을 받아오는 동안, packet 4번의 데이터는 보관된다. 그리고 나머지 상관없는 stream1의 패킷에는 지연이 발생하지 않는다. 오로지 Stream 2번과 관련된 패킷에만 지연이 생긴다.

이런 원리를 통해서 http3에서는 TCP 차원에서 발생하던 HOLB의 문제를 해결했습니다.

모든 패킷들에 대해서 순서를 지키도록 하는 것은 아니고, 각 스트림에 대해서는 순서를 지키도록 하면서 QUIC은 신뢰성을 보장하고 있습니다.

요약:

• 스트림 = 개별 파일
• 2.0에서는 멀티플렉싱으로 하나의 tcp에서 여러 파일을 받을수 있게됨.
  • 이전에는 파일마다 연결이 필요 했음.
  • 좋긴한데 stream1에서 패킷 손실이 발생하면 다른 streamK의 패킷들도 지연되는 문제가 있었음. (TCP레벨에서의 Head Of Line Blocking 문제)
• 3.0에서는 이 마저도 해결함.
  • 각각의 streamK들은 패킷 손실이 발생해도 서로 독립적으로 지연됨.

:BONUS: TCP와 UDP를 대화 타입에 비유

TCP => 우리 어디까지 이야기했더라? 반응 주고 받으며 계속 확인하는 사람.

• 대화의 질은 좋지만 대화하는데 에너지가 많이 들어감, 특히 여러명이 말걸때.
• 확인하는 과정이 곧 추가적인 비용이고 따라서 비용이 큰 방법.

UDP => 자기 할 말만 계속 하는사람.

• 대화는 아니지만 말하는 사람은 편하게 자기하고 싶은 이야기 말할수 있음.
• 사용 체력 대비 많은 말을 할수 있음.
• 상대방 반응 확인할 시간 아껴서 빠름.
• 기본적으로 단방향 통신이지만, 애플리케이션 레벨에서 송수신 잘 처리하면 양방향 통신도 가능하다.
• 사용 분야: (realTimeService) 통화, 온라인 게임, 스트리밍 서비스
• 이유 예시) 통화를 TCP로 했을때
  • ㄱ: 너 나 좋아해?
  • ㄴ: ...(TCP 느려서 아무것도 못 들어서 침묵중)
  • ㄱ: 왜 말이 없어? 나 싫어해?
  • ㄴ: 응! (ㄱ: 너 나 좋아해?가 이제 도착하고 그에대한 대답)
  • 실시간 소통이 안될경우 대화가 꼬여서 대참사가 발생할수 있다.

✨레퍼런스

• https://velog.io/@yesbb/HTTP3까지-버전별-변천사
• https://medium.com/rate-labs/quic-프로토콜-구글-또-너야-932befde91a1

https://www.acmicpc.net/problem/14891

문제 소개 및 재정의

1. 4개의 톱니바퀴가 있다.
2. 톱니의 개수는 8개이다. (1번 톱니~8번 톱니)
3. 톱니에는 자성이 있다. N극과 S극
4. 톱니 8개의 자성 배치는 케이스마다 다르다.
5. 톱니바퀴(기어) 4개는 나란히 붙어있다.
6. 왼쪽 톱니바퀴의 3번 톱니와 오른쪽 톱니의 7번 톱니는 인접해있다.
7. 왼쪽 톱니바퀴의 3번 톱니와 오른쪽 톱니바퀴의 7번 톱니의 극성이 서로 반대일때, 하나가 회전하면 다른 하나는 반대 방향으로 회전한다.

문제 패턴

시뮬레이션으로 구현하는 방법이 일반적이다.

어떻게 풀까? - 시뮬레이션

포인트

톱니바퀴의 구현

먼저 톱니바퀴를 뭐로 구현할지 고민했다.

• 1*8 배열 장점: 톱니바퀴와 회전의 구현이 간편하다. 단점: 회전시 업데이트 비용이 톱니의 개수에 비례한다.
• 3*3 배열 장점: 시각적으로 눈에 잘 들어온다. 논리적으로 직관적이다. 단점: 회전시 인덱스를 바꿔주는 로직이 추가로 필요하다. 업데이트 비용이 톱니의 개수에 비례한다.
• Deque 장점: 톱니바퀴와 회전의 구현이 간편하다. 회전시 업데이트 비용이 상수다. 단점: 회전을 전파시킬때 3번 톱니와 7번 톱니의 값을 알아야 하는데 이것이 번거롭다. . 고민결과 1*8로 결정했다. 이유는 구현이 간편하고 비용은 문제를 푸는데 방해되지 않기 때문이다.

톱니바퀴의 회전구현

값들을 회전방향으로 한칸씩 밀어버리고 마지막 값만 스왑하는 방식으로 구현할수 있다.

배열을 깊은 복사해서 회전방향에 맞게 인덱스를 계산하고 원본의 인덱스에 값을 넣어주는 방식도 있다. 이 방식이 위의 방식보다는 메모리와 시간복잡도 손해가 발생하지만, 코드가 간결해지기에 이 방법을 선택했다. 메모리와 시간복잡도도 현재 문제의 입력크기를 능히 소화할수 있다.

여기서 조금만 최적화를 하고싶다면 .clone을 사용하지 말고. Static으로 선언한 배열을 for문으로 복사해주면 메모리 사용량은 최적화할수 있을것이다.

시계방향(+1)으로 회전시 오버플로우를 구현해야한다. 0번(1번) => 1번 1번 => 2번 2번 => 3번 3번 => 4번 4번 => 5번 5번 => 6번 6번 => 7번 7번 => 0번 i번째 톱니는 (i+1)%8번째 톱니의 자리로 이동하게 된다.

• 다음 위치로 이동시키기 위해서 +1을 해주고.
• 오버플로우를 구현시키기 위해서 %8을 해준다.

반시계방향(-1)으로 회전시 언더플로우를 구현해야한다. 0번 => 7번 1번 => 0번 2번 => 1번 3번 => 2번 4번 => 3번 5번 => 4번 6번 => 5번 7번 => 6번 i번째 톱니는 (i-1+8)%8번째 톱니의 자리로 이동하게 된다.

• 다음 위치로 이동시키기 위해서 -1을 해주고.
• -1 해주면서 음수로 떨어지는 언더플로우 발생시 맨뒤로 보내주기 위해서 전체 길이인 +8을 더해준다.
• 언더플로우를 구현시키기 위해서 %8을 해준다.

회전 코드

static void rotate(int gear, int direction) {
    int[] tempOrigin = gears[gear].clone();

    if(direction == 1) {
        for (int i = 0; i < tempOrigin.length; i++) {
            gears[gear][(i+1)%8] = tempOrigin[i];     // 임시로 저장해둔 원본에서 0번 위치는 1번으로 움직이고 1번 위치는 2번으로 움직여야한다. 
                                                    // 이 규칙이 6번까지는 유지되지만, 7번은 0번으로 가야하므로 8로 나눈 나머지를 사용한다. 
                                                    // 이렇게 하면 0~6번까지도 결과에 변화가 없다. 
        }
    } else { // direction == -1
        for (int i = 0; i < tempOrigin.length; i++) {
            gears[gear][(i-1+8)%8] = tempOrigin[i];     // 임시로 저장해둔 원본에서 0번 위치는 7번으로 움직이고, 나머지는 자기 위치보다 앞으로 움직인다. (0->7, 1->0,... 7->6)
        }
    }
}

그런데 회전방향이 1일때 +1을 해주고, -1일때 -1을 해주는 것에서 둘을 합칠수 있다는 생각이 들었다. (i+1)%8 => (i+1+8)%8로 바꾸어도 +8은 %8로인해 0이 되기 때문에 지장이 안생긴다. 후의 회전전파 단계에서 회전하지 않는 기어들도 회전방향을 0으로 주어서 일괄적으로 회전시키는데, 이때도 지장없다. . 만약 회전방향에 따라 코드를 분리한다고 하면, 회전전파 단계를 고려하여서 반시계방향으로 회전할때를 else가 아닌 else if (direction==-1)로 처리해주어야 한다.

향상된 회전 코드

static void rotate(int gear, int direction) {
    int[] tempOrigin = gears[gear].clone();
    for (int i = 0; i < tempOrigin.length; i++) {
        gears[gear][(i+direction+8)%8] = tempOrigin[i]; 
    }
}

톱니바퀴 회전 전파 구현

한 기어가 회전할때 어디까지 같이 회전하는지 미리 알아야한다. 기어는 동시에 회전하기 때문이다. 따라서 모든 기어의 회전방향을 배열에 담아서 기록한다. . 따라서 선택된 기어를 기준으로 왼쪽 방향으로 전파시켜본다. 함께 돌아가지 않는 기어를 만날때까지 왼쪽으로 타고 넘어간다. 서로 반대 방향으로 기어가 회전하므로, 넘어갈때마다 회전 방향을 -1을 곱해줘야한다. 그리고 그 값을 배열 기록한다. 맨 왼쪽 기어인 0번 기어에 도착하면 더 이상 함께 돌아갈 기어가 없으므로 멈춘다. . 위 과정을 오른쪽 방향으로 전파시킨다. 오른쪽으로 타고 넘어가면서 함께 회전하는 기어를 만날때마다 회전방향을 반대로(*-1) 해주고 그 값을 회전방향을 기록하는 배열에 기록한다. 함께 돌아가는 않는 기어를 만나거나, 맨 오른쪽 기어인 4번 기어에 도착하면. 더 이상 함께 돌아갈 기어가 없으므로 중단한다. . 기어가 함께 돌아갈지 여부는 3번과 7번톱니의 극성이 같은지 여부로 판단한다. . 왼쪽과 오른쪽으로의 전파가 끝났다면, 모든 기어의 회전방향을 파악한 상태이므로 모든 기어를 각자의 회전방향으로 회전시킨다.

회전 전파 코드

static void canRotateThenDo(int selectedGear, int direction) {
    int[] temp = new int[4];            // 각 기어의 회전방향은 0으로 초기화돼있음. 회전이 전파 안된 기어는 값이 0이라 회전안함.
    temp[selectedGear] = direction;

    // 오른쪽으로 확장(전파)
    int point = selectedGear;             // 시작 기어의 위치 => 오른쪽으로 넘어갈때마다 +1돼야함.
    int nowDirection = direction;        // 시작 기어의 회전방향 => 오른쪽으로 넘어갈때마다 *-1돼야함.
    while(true) {
        if(point==4-1)                     // 4번 기어는 비교할 오른쪽 기어가 없기 때문에 반복문 탈출
            break;
        if(gears[point][3-1]!=gears[point+1][7-1]) { // 서로 다른 극이므로 오른쪽으로 넘어갈수 있음. 
            point +=1;
            nowDirection = nowDirection*-1;
            temp[point] = nowDirection;    // 회전이 전파된 기어자리에 회전방향 저장해두기.
        } else {                         // 회전이 전달안되므로 탈출
            break;
        }
    }

    // 왼쪽으로 확장(전파)
    point = selectedGear;                 // 시작 기어의 위치 => 왼쪽으로 넘어갈때마다 -1돼야함.
    nowDirection = direction;            // 시작 기어의 회전방향 => 왼쪽으로 넘어갈때마다 *-1돼야함.
    while(true) {
        if(point==1-1)                     // 1번 기어는 비교할 왼쪽 기어가 없기 때문에 반복문 탈출
            break;
        if(gears[point-1][3-1]!=gears[point][7-1]) { // 서로 다른 극이므로 왼쪽으로 넘어갈수 있음. 
            point -=1;
            nowDirection = nowDirection*-1;
            temp[point] = nowDirection;    // 회전이 전파된 기어자리에 회전방향 저장해두기.
        } else {                         // 회전이 전달안되므로 탈출
            break;
        }
    }

    // 전부 회전시키기.
    for (int i = 0; i < temp.length; i++) {
        rotate(i, temp[i]);
    }
}

전체 코드

import java.io.*;
import java.util.*;
public class BOJ_14891_톱니바퀴6 {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;


    // 세팅
    static int[][] gears;
    static int[][] cmd; // 대상 톱니 / 회전 방향
    static int sum;
    static int K;

    // 메소드

    //// 회전 판정
    static void canRotateThenDo(int selectedGear, int direction) {
        int[] temp = new int[4];            // 각 기어의 회전방향은 0으로 초기화돼있음. 회전이 전파 안된 기어는 값이 0이라 회전안함.
        temp[selectedGear] = direction;

        // 오른쪽으로 확장(전파)
        int point = selectedGear;             // 시작 기어의 위치 => 오른쪽으로 넘어갈때마다 +1돼야함.
        int nowDirection = direction;        // 시작 기어의 회전방향 => 오른쪽으로 넘어갈때마다 *-1돼야함.
        while(true) {
            if(point==4-1)                     // 4번 기어는 비교할 오른쪽 기어가 없기 때문에 반복문 탈출
                break;
            if(gears[point][3-1]!=gears[point+1][7-1]) { // 서로 다른 극이므로 오른쪽으로 넘어갈수 있음. 
                point +=1;
                nowDirection = nowDirection*-1;
                temp[point] = nowDirection;    // 회전이 전파된 기어자리에 회전방향 저장해두기.
            } else {                         // 회전이 전달안되므로 탈출
                break;
            }
        }

        // 왼쪽으로 확장(전파)
        point = selectedGear;                 // 시작 기어의 위치 => 왼쪽으로 넘어갈때마다 -1돼야함.
        nowDirection = direction;            // 시작 기어의 회전방향 => 왼쪽으로 넘어갈때마다 *-1돼야함.
        while(true) {
            if(point==1-1)                     // 1번 기어는 비교할 왼쪽 기어가 없기 때문에 반복문 탈출
                break;
            if(gears[point-1][3-1]!=gears[point][7-1]) { // 서로 다른 극이므로 왼쪽으로 넘어갈수 있음. 
                point -=1;
                nowDirection = nowDirection*-1;
                temp[point] = nowDirection;    // 회전이 전파된 기어자리에 회전방향 저장해두기.
            } else {                         // 회전이 전달안되므로 탈출
                break;
            }
        }

        // 전부 회전시키기.
        for (int i = 0; i < temp.length; i++) {
            rotate(i, temp[i]);
        }
    }

    //// 회전
    static void rotate(int gear, int direction) {
        int[] tempOrigin = gears[gear].clone();
        for (int i = 0; i < tempOrigin.length; i++) {
            gears[gear][(i+direction+8)%8] = tempOrigin[i];     // 8은 더해도 %8로 사라지는 부분이기 때문에 +1 로직에서도 정상적으로 작동한다. -1로직을 위해 +8을 하는 것이다.
        }
    }

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력

        //// 기어 입력
        gears = new int[4][8];
        for (int i = 0; i < 4; i++) {
            char[] cList = input.readLine().toCharArray();
            for (int j = 0; j < cList.length; j++) {
                gears[i][j] = Character.getNumericValue(cList[j]);
            }
        }
        //// 커맨드 입력
        K = Integer.parseInt(input.readLine());
        cmd = new int[K][2];
        for (int k = 0; k < K; k++) {
            tokens = new StringTokenizer(input.readLine());
            cmd[k][0] = Integer.parseInt(tokens.nextToken()) -1;    // 기어번호를 인덱스번호와 맞춤.
            cmd[k][1] = Integer.parseInt(tokens.nextToken())   ;
        }
        // 세팅
        // 작업
        for (int i = 0; i < cmd.length; i++) {
            int selectedGear = cmd[i][0];
            int direction = cmd[i][1];
            canRotateThenDo(selectedGear, direction);
        }

        sum = 0;
        for (int i = 0; i < gears.length; i++) {
            if (gears[i][0] == 1){ // i번 기어의 12시 방향이 S극(1)이면 2의 i승을 더해준다.
                sum += (int) Math.pow(2,i);
            }
        }
        // 출력
        System.out.println(sum);
    }

}

퍼포먼스

[ 11,852 KB | 64 ms ]

마무리

컨디션이 안 좋아서 잔 실수를 많이했다. 컨디션 관리를 잘 하자...

// 인덱스값을 서로 바꿔서 넣었다.
static void rotate(int gear, int direction) {
    for (int i = 0; i < tempOrigin.length; i++) {
        gears[gear][i] = tempOrigin[(i+direction+8)%8]; 
    }
}

// 와일문 안에서 수정해가면서 사용할 변수를 와일문 안에서 선언했다...
// nowDirection = direction*-1; 가 아니라 
// nowDirection = nowDirection*-1; 이어야 한다.
static void canRotateThenDo(int gearSelcted, int direction) {
        int[] temp = new int[4]; // 0으로 초기화돼있음. 회전이 전파 안된 기어는 값이 0이라 회전안함.
        temp[gearSelcted] = direction;

        // 오른쪽으로 이동
        while(true) {
            int point = gearSelcted;         // 시작 기어의 위치 => 오른쪽으로 확장될때마다 +1돼야함.
            int nowDirection = direction;    // 시작 기어의 회전방향 => 오른쪽으로 넘어갈때마다 *-1돼야함.
            if(point==4-1) // 4번 기어는 비교할 오른쪽 기어가 없기 때문에 반복문 탈출
                break;
            if(gears[point][3-1]!=gears[point+1][7-1]) { // 서로 다른 극이므로 오른쪽으로 넘어갈수 있음. 
                nowDirection = direction*-1;
                point +=1;
                temp[point] = nowDirection;    // 회전이 전파된 기어의 회전방향 저장해두기.
            } else { // 회전이 전달안되므로 탈출
                break;
            }
        }

https://www.acmicpc.net/problem/2961

문제 소개 및 재정의

N개의 재료로 만들수 있는 모든 조합을 구한다. 조합별로 신맛과 쓴맛을 구한뒤 두 맛의 차이를 구한다. 신맛은 재료별로 곱해주고 쓴맛은 재료별로 더해준다. 맛의 차이가 가장 적은것을 제출한다.

문제 패턴

N개의 재료로 만들수 있는 모든 조합을 구해야 한다. 따라서 부분집합을 사용해야한다. 부분집합에서 공집합은 문제에서 제외하라고 한다. 부분집합별로 음식의 두가지 맛을 계산해서 그 차이를 구하고. 최소값과 비교해서 최소값을 업데이트 해준다.

어떻게 풀까? - 완전탐색

포인트

재료 pool에서 부분집합을 재귀적으로 생성했다. 바닥조건에 닿을때마다 boolean 배열로 부분집합이 생성된다. 이때, 배열을 순회하면 값이 true(포함)인 재료들의 맛을 계산해준다. 부분집합마다 음식의 맛을 계산해서 그 차이를 최소값과 비교한다.

최악의 경우 식재료는 10개, 모든 식재료의 쓴맛과 신맛의 값이 $$10^9$$ 일수있다. 대략적으로 $$10^3 = 2^{10}$$ 이므로 이렇게 계산을 하겠다. . 이 경우 쓴맛은 $$10^910 = 102^{30}$$의 정수값을 가진다. 이 값은 long 타입으로 커버가 가능한 값이다. 사실 int의 최대값을 21억에 근사하므로 100억은 커버 못한다는 사실을 금방 알수있다. . 신맛의 경우에는 $$(10^9)^{10} = 10^{90} = 2^{300}$$으로 대략 300비트 이상을 저장할수있는 자료형이 필요하다. long은 64-1비트의 양수까지만 저장할수 있으므로 더 큰 자료형이 필요하다. 그래서 BigInteger 자료형을 사용했다.

BigInteger를 사용하기 위해서 사용한 레퍼런스

• https://inpa.tistory.com/entry/JAVA-%E2%98%95-BigInteger-BigDecimal-%EC%9E%90%EB%A3%8C%ED%98%95-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%B4%9D%EC%A0%95%EB%A6%AC#biginteger_%EC%9E%90%EB%A3%8C%ED%98%95
• https://blog.naver.com/asap0628/220722382104

전체 코드 - 클린 버전

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


public class BOJ_2961_도영이가_만든_맛있는_음식 {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;

    // 세팅
    static int N;
    static int[][] origin; // new int[N][2]
    static boolean[] subset;
    static boolean miniIsFirst = true;
    static BigInteger mini;

    // 메서드
    // 부분집합 구하기
    static void makeSubset(boolean[] leaf, int nowDigit, final int targetDigit) {
        // 바닥 조건
        if(nowDigit>=targetDigit) {
            // 추가작업
            calc();
            return;
        }

        // 재귀 파트
        leaf[nowDigit] = false;        // 미포함
        makeSubset(leaf, nowDigit+1, targetDigit);
        leaf[nowDigit] = true;        // 포함
        makeSubset(leaf, nowDigit+1, targetDigit);
    }

    // 각각의 부분집합에서 계산하기
    static void calc() {
        boolean token = false;
        BigInteger S = BigInteger.valueOf(1);
        BigInteger B = BigInteger.valueOf(0);

        // 부분집합의 값들 계산
        for(int i=0; i<N; i++) {
            if(subset[i]==false)    
                continue;
            token = true; // 반복문이 끝날때까지 token이 false면 공집함임을 의미함.
            // subset[i]==true일때 로직
            BigInteger Si = BigInteger.valueOf(origin[i][0]);
            BigInteger Bi = BigInteger.valueOf(origin[i][1]);
            S = S.multiply(Si);
            B = B.add(Bi);
        }
        if(token==false)
            return;
        BigInteger gap = B.subtract(S);
        gap = gap.abs(); 
        if(miniIsFirst) {
            mini = gap;
            miniIsFirst = false;
        } else { // 최소값 초기화 성공 이후
            mini = mini.min(gap);
        }
    }

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        N = Integer.parseInt(input.readLine());
        origin = new int[N][2];
        for(int i=0; i<N; i++) {
            tokens = new StringTokenizer(input.readLine());
            int Si = Integer.parseInt(tokens.nextToken());
            int Bi = Integer.parseInt(tokens.nextToken());
            origin[i][0] = Si;
            origin[i][1] = Bi;
        }
        subset = new boolean[N];
        // 세팅
        // 작업
        makeSubset(subset, 0, N);
        // 출력
        System.out.println(mini);
    }

}

전체 코드 - 주석 버전

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


public class BOJ_2961_도영이가_만든_맛있는_음식 {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;

    // 세팅
    static int N;
    static int[][] origin; // new int[N][2]
    static boolean[] subset;
    static boolean miniIsFirst = true;
    static BigInteger mini;

    // 메서드
    // 부분집합 구하기
    static void makeSubset(boolean[] leaf, int nowDigit, final int targetDigit) {
        // 바닥 조건
        if(nowDigit>=targetDigit) {
            // 추가작업
            calc();
            return;
        }

        // 재귀 파트
        leaf[nowDigit] = false;        // 미포함
        makeSubset(leaf, nowDigit+1, targetDigit);
        leaf[nowDigit] = true;        // 포함
        makeSubset(leaf, nowDigit+1, targetDigit);
    }

    // 각각의 부분집합에서 계산하기
    static void calc() {
        // 처음값 넣기 위함.

        // 신맛과 쓴맛은 자연수이기 때문에 처음에 0으로 시작해도 된다. 마지막에도 값이 0이면 공집합이라는 뜻이므로 버린다. 
        // => 그렇지 않다. 쓴맛은 곱하기이므로 1부터 시작해야한다. 공집합 처리는 그냥 token을 사용하자.
        // => 쓴맛이 합이고 신맛이 곱이다... 반대로 착각하는 이슈가 있었다...
        boolean token = false;
        BigInteger S = BigInteger.valueOf(1);
        BigInteger B = BigInteger.valueOf(0);

        // 부분집합의 값들 계산
        for(int i=0; i<N; i++) {
            if(subset[i]==false)    // 코드 가독성을 위해서 인덴트 뎁스를 낮추는 차원에서 false일때 버린다. true일때 계산하기 위해서
                continue;
            token = true; // 반복문이 끝날때까지 token이 false면 공집함임을 의미함.
            // subset[i]==true일때 로직
            BigInteger Si = BigInteger.valueOf(origin[i][0]);
            BigInteger Bi = BigInteger.valueOf(origin[i][1]);
            S = S.multiply(Si);         // 계산 값을 S에 다시 저장 안해줘서 gap이 1만 나오는 이슈가 있었음... BigInteger 낯설다...
            B = B.add(Bi);    // 계산 값을 B에 다시 저장 안해줘서 gap이 1만 나오는 이슈가 있었음... BigInteger 낯설다...
        }
        if(token==false) // 공집합 버림 token ==true일때 버렸던 이슈가 있었음... 단순 착오
            return;
        BigInteger gap = B.subtract(S); // B는 곱하기로 커지고 S는 더하기로 커지므로 무조건 B가 더 크다. => 반례가 있을지도 모르니 속 편하게 절대값 구하자.
        gap = gap.abs(); // 절대값을 gap에 저장해주지 않는 이슈가 있었다...
//        System.out.println(S+" | "+ B+" | "+gap +" | "+mini);
        if(miniIsFirst) {
            mini = gap;
            miniIsFirst = false;
        } else { // 최소값 초기화 성공 이후
            mini = mini.min(gap);
        }
    }

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        N = Integer.parseInt(input.readLine());
        origin = new int[N][2];
        for(int i=0; i<N; i++) {
            tokens = new StringTokenizer(input.readLine());
            int Si = Integer.parseInt(tokens.nextToken());
            int Bi = Integer.parseInt(tokens.nextToken());
            origin[i][0] = Si;
            origin[i][1] = Bi;
        }
        subset = new boolean[N];
        // 세팅
        // 작업
        makeSubset(subset, 0, N);
        // 출력
        System.out.println(mini);
    }

}

퍼포먼스

[ 12,840 KB | 76 ms ]

마무리

문제를 끊김없이 푼게 아니고 문제를 읽어두고, 다음날 코드를 짰다. 그러다보니 문제를 잘못 이해한 이슈가 조금 있었다. BigInteger 사용이 어색해서 값을 저장하는 것을 깜빡하는 이슈가 있었다.

시간이 제일 짧은 자바코드를 보니까 음식의 신맛과 쓴맛을 int타입에 저장해서 풀었다. 저렇게해서 풀릴거면 입력을 왜 저렇게 만들었을까? 테스트가 충분하지 않은 문제라는 생각이 들었다.

https://www.acmicpc.net/problem/1541

문제 소개 및 재정의

+와 - 연산만 있는 식의 값을 최소화 하시오. 피연산자는 모두 양수이고, 임의대로 괄호를 추가할수 있다.

문제 패턴

처음에 두가지의 생각이 들었다.

• 괄호를 치는 모든 경우의 수를 구해서 완전탐색으로 푸는 것
• 최소값이 되는 규칙을 찾아서 푸는것

어떻게 풀까? - 완전 탐색

포인트

괄호를 치는 것을 구현하는게 너무 어려웠다. 고민 끝에 아래와 같은 결론을 얻었다.

• 괄호를 친다. <=> 연산 순서를 결정한다.
• 연산자에 번호를 매긴다음에 순열을 만든다 => 연산 순서를 결정한다
• 연산자에 번호를 매긴다음에 순열을 만든다 => 괄호를 친다

따라서 연산자의 개수를 길이로 가지는 순열을 만들었다. 그런데 문제에서 최악의 경우 연산자의 개수는 24개이다. 시간복잡도가 24!인 것인데.... 순열의 시간복잡도를 착각하지 않았더라면 시간복잡도가 너무 커서. 완전탐색 풀이를 포기했을것 같다. 이런 말을 하는 이유는 착각했기 때문이다.

구현 시 어려웠던 점. 연산할때마다 피연산자는 연산결과값으로 덩어리로 뭉치게됨.

하나로 합쳐졌으니 인덱스를 삭제해볼까? 그러면 피연산자리스트의 인덱스와 연산자 인덱스의 조화가 어그러진다. 그리고 리스트의 삭제 연산은 비용이 비싸서 다른 방법을 생각해봤다.

연산할때마다 나온 결과값을, 같은 덩어리로 합쳐진 피연산자 위치에 마스킹 하는 것이다. 그러면 계산이 정확해진다. 그러기 위해서는 같은 덩어리를 찾기 위해서 DFS를 할 필요가 있다. DFS를 하기 위해서 현재 연산이 몇번째(i)로 하는중인지 그 값으로 방문배열 상에서의 덩어리들을 마스킹 할 필요가 있었다. 그러면 연산을 처음하는 피연산자는 바로 i로 저장하고. 아니라면 DFS로 자기랑 같은 덩어리 번호인것들만 타고가면서 i로 저장한다. 그럼 또 같은 덩어리가 기록된다.

하지만 다시 생각해보니 연산자의 크기가 최대 24이므로 그냥 리스트에서 인덱스를 삭제해도 될것 같다. 피연산자리스트에서 리스트를 삭제할때, 해당 위치의 연산자 리스트의 인덱스도 삭제해주는 방식으로. 시간이 많이 소요되지 않는것 같아서 좋다. 위의 방법은 너무 구현하기 힘들다.

샘플 테케는 잘 통과했지만, 실제 채점에서는 1% 이후에 시간초과가 발생했다.

코드

// 어디까지 마스킹할지가 너무 어려운데영....
import java.io.*;
import java.util.*;

public class Main {

    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    // 세팅
    static ArrayList<Integer> operandList;
    static ArrayList<Character> operatorList;
    static int[] operandVisited;
    static int[] work;
    static int mini = Integer.MAX_VALUE;
    // 메소드

    //// 연산자 기준 순열 생성 => 연산 순서 생성 => 정상 작동 확인
    static void makePermu(int[] leaf, int nowDigit, final int targetDigit, final int pool, boolean[] visited) {
        // 바닥 조건
        if(nowDigit>=targetDigit) {
            // 추가 작업
            reset();
            // 전체 연산
            for (int i = 0; i < leaf.length; i++) {
                int operatorIndex = leaf[i];
                int maskingValue;
                if(operatorList.get(operatorIndex)=='+') {
                    maskingValue = work[operatorIndex]+work[operatorIndex+1];
                } else {
                    maskingValue = work[operatorIndex]-work[operatorIndex+1];
                }
                // 방문처리 + 값 마스킹 처리
                int left = operandVisited[operatorIndex];
                int right = operandVisited[operatorIndex+1];
                if(left==-1) {
                    operandVisited[operatorIndex] = i;
                    work[operatorIndex] = maskingValue;
                } else {
                    DFS(operatorIndex, left, i, maskingValue);
                }

                if(right==-1) {
                    operandVisited[operatorIndex+1] = i;
                    work[operatorIndex+1] = maskingValue;
                } else {
                    DFS(operatorIndex+1, right, i, maskingValue);
                }
            }
            // work의 모든 값이 연산 최종결과가 됨.
            mini = Math.min(mini, work[0]);
            return;
        }

        // 재귀 파트
        for(int i=0; i<pool;i++) {
            if(visited[i]) // 사용한 인덱스면 점프
                continue;
            visited[i] = true;
            leaf[nowDigit] = i;
            makePermu(leaf, nowDigit+1, targetDigit, pool, visited);
            visited[i] = false;
        }
    }

    //// 연산결과 마스킹 용도
    static void DFS(int x, final int compare, final int maskingIndex ,final int maskingValue) {  // 둘중의 최소값 골라서. 
        // 범위 초과시 버림 ==> DFS 타기 전에 해줄수도 있음. 동작 잘 안되면 여기부터 조지기.
        if(x<0 || x>operandList.size()-1)
            return;
        // 바닥 조건
        if(operandVisited[x]!=compare) // 비교값(compare)이랑 같을때만 확장. 비교값이랑 달라지면 확장불가!
            return;
        // 방문 처리가 아닌 마스킹
        operandVisited[x] = maskingIndex;
        work[x] = maskingValue;

        // 재귀 파트
        DFS(x-1, compare, maskingIndex, maskingValue);
        DFS(x+1, compare, maskingIndex, maskingValue);
    }

    //// 연산을 위한 재료 세팅
    static void reset() {
        Arrays.fill(operandVisited, -1);
        for (int i = 0; i < operandList.size(); i++) {
            work[i] = operandList.get(i);
        }
    }

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        operandList = new ArrayList<>();
        operatorList = new ArrayList<>();

        tokens = new StringTokenizer(input.readLine(),"-+",true);
        for (int i = 0; ; i++) { // 무한루프
            if(tokens.hasMoreTokens()==false) { // 더 이상 토큰이 없으면 탈출
                break;
            }
            if(i%2==0) { // 짝수번째는 피연산자임. origin 리스트에 분류하기.
                int operand = Integer.parseInt(tokens.nextToken());
                operandList.add(operand);
            } else { // 홀수번쨰는 연산자임. operator 리스트에 분류하기.
                char operator = tokens.nextToken().charAt(0);
                operatorList.add(operator);
            }
        }
        // 세팅
        operandVisited = new int [operandList.size()];
        work = new int[operandList.size()];
        // 작업
        makePermu(new int[operatorList.size()], 0, operatorList.size(), operatorList.size(), new boolean[operatorList.size()]);
        // 출력
        System.out.println(mini);
    }

}

어떻게 풀까? - 수학

포인트

더하거나 빼기만 하는 식에서 최소값을 구하려면? 빼기 뒤에 있는 피 연산자를 최대한 크게 만들면 된다. 그러기 위해서는 빼기 뒤의 더하기를 먼저 계산해두면 된다. 빼기가 나올때까지는 수를 더해 나간다. 그리고 빼기가 나오면 그때부터 다시 새롭게 수를 더해 나간다. 그러면 값이 [양수, 음수, 음수, ... ,음수] 로 구성된다. 이 순서대로 계산해주면 전체식의 최소값이 나온다.

입력이 조금 까다로운 문제였는데 StringTokenizer에서 구분자 단위로 끊고 구분자도 포함시키는 메소드가 있어서 손쉽게 파싱했다. ✨ 레퍼런스: https://reakwon.tistory.com/90

코드

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

public class Main {

    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    // 세팅
    static ArrayList<Integer> operandList;
    static ArrayList<Character> operatorList;
    static ArrayList<Integer> subSums;
    // 메소드



    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        operandList = new ArrayList<>();
        operatorList = new ArrayList<>();
        subSums = new ArrayList<>();

        tokens = new StringTokenizer(input.readLine(),"-+",true);
        for (int i = 0; ; i++) { // 무한루프
            if(tokens.hasMoreTokens()==false) { // 더 이상 토큰이 없으면 탈출
                break;
            }
            if(i%2==0) { // 짝수번째는 피연산자임. origin 리스트에 분류하기.
                int operand = Integer.parseInt(tokens.nextToken());
                operandList.add(operand);
            } else { // 홀수번쨰는 연산자임. operator 리스트에 분류하기.
                char operator = tokens.nextToken().charAt(0);
                operatorList.add(operator);
            }
        }
        // 세팅

        // 작업
        int sum =0;
        sum += operandList.get(0);     // 첫번째꺼는 미리 더해놓기 그래야 더하는 로직이 단순해짐. 지금 시점 하나만 더하면 되니까. 
                                    // 안 그러면 반복문에서 처음에 두개 더해야되는데 뒤에서도 같은 로직 쓰면서 계속 1번씩 중복해서 더해짐.
        for (int i = 0; i < operatorList.size(); i++) {
            if(operatorList.get(i) == '-') { // 연산자가 -가 나오기 전까지는 계속 더한다. -가 나오면 지금까지 더해놓은거 subSums에 저장하기. 
                subSums.add(sum);     // -가 나오면 지금까지 더해놓은거 저장하기. 
                sum = 0;            // 다시 처음부터 더하기 위해서 초기화하기.
            }
            sum += operandList.get(i+1); 
        }
        // 마지막 한덩어리도 add
        subSums.add(sum);

        // 값 계산. 첫번째만 양수고 나머지는 다 음수이므로 빼줌.
        int answer = subSums.get(0);
        for (int i = 0+1; i < subSums.size(); i++) {
            answer -= subSums.get(i);
        }
        // 출력
        System.out.println(answer);
    }
}

퍼포먼스

[ 11,588 KB | 64 ms ]

마무리

퍼뮤테이션을 오랜만에 써서 시간복잡도가 끔찍하게 크다는 사실을 간과했다... 구현하는거 힘들었다... StringTokenizer를 더 잘 쓸수 있게 되어 좋았다.

https://www.acmicpc.net/problem/14889

문제 소개 및 재정의

N명의 선수들을 절반으로 나눠서 팀을 만들고. 팀별로 멤버간 시너지의 총계를 구해서, 둘의 차이의 최소값을 구하시오.

문제 패턴

N명중에서 N/2명을 뽑아서 팀을 만들어라 => 조합 팀 멤버의 순서쌍을 만들어라 => 중복순열

어떻게 풀까? - 완전 탐색

포인트

먼저 조합으로 팀 하나를 만든다. 전체 선수 풀에서 만든 팀의 선수들을 빼서, 상대팀을 만든다.

팀이 만들어지면, 팀내에서 선수들을 둘씩 묶는 모든 경우의 수를 만든다. (순서가 있음) 각 경우의 수에 해당되는 값을 테이블에서 찾아서 더해주면 시너지 총계가 된다.

시너지총계의 차이를 구하고 계속 비교하며 최소값을 업데이트한다.

모든 경우의 수(조합)에 대해서 수행한다.

코드

package study.week9;

// 전략! 20명에서 10명을 조합으로 뽑아서 팀을 만들고
// 팀 조합 만들어질때마다 상대 팀 조합도 임시로 만든다.
// 각 팀의 시너지를 구하는 메소드는 10명중에 2명을 중복순열로 뽑는 메소드로 구현한다.

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

public class BOJ_14889_스타트와_링크 {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;

    // 세팅
    static int N;
    static int[][] origin;
    static int[] team;
    static int[] rival;
    static int[] playerPool;

    static int[] synergyPair = new int[2];
    static int teamSynergy;  // 사이클마다 초기화
    static int rivalSynergy; // 사이클마다 초기화
    static int mini = Integer.MAX_VALUE;

    // 메소드
    //// 조합 생성
    static void makeCombi(int[] leaf, int nowDigit, final int targetDigit, final int pool, int start) {
        // 바닥 조건
        if(nowDigit >= targetDigit) {
            // 작업 추가
//            System.out.println(Arrays.toString(leaf));
            // team 결정된 상태, rival 생성
            makeRival();
            // 팀별 시너지 계산, 계산전 시너지 총계 초기화
            teamSynergy =0;
            rivalSynergy =0;
            makePI(synergyPair, 0, 2, team, 1);
            makePI(synergyPair, 0, 2, rival, 2);
            // 팀별 시너지 차이값 계산 후 최소값 업데이트
            int gap = Math.abs(teamSynergy - rivalSynergy);
            mini = Math.min(mini, gap);
            return;
        }

        // 재귀 파트
        for (int i = start; i < pool+1; i++) {
            leaf[nowDigit] = i;
            makeCombi(leaf, nowDigit+1, targetDigit, pool, i+1);
        }

    }

    //// 상대팀 만들기
    static void makeRival() {
        // playerPool 초기화
        for (int i = 0; i < playerPool.length; i++) {
            playerPool[i]=i;
        }
        // team 지우기
        for (int i = 0; i < team.length; i++) {
            int del = team[i];
            playerPool[del] =0;
        }
        // playerPool 정렬후 클로닝
        Arrays.sort(playerPool);
        rival = Arrays.copyOfRange(playerPool, (N/2)+1, N+1); // 포문으로 값만 바꾸면 최적화
    }

    //// 중복순열로 팀의 시너지 계산
    static void makePI(int[] leaf, int nowDigit, final int targetDigit, final int[] poolTeam, int indicator) {
        // 바닥 조건
        if(nowDigit>= targetDigit) {
            // 추가 작업
            if(indicator ==1) {
                teamSynergy += origin[leaf[0]-1][leaf[1]-1];
            } else if(indicator ==2) {
                rivalSynergy += origin[leaf[0]-1][leaf[1]-1];
            }

            return;
        }
        // 재귀 파트
        for (int i = 0; i < poolTeam.length; i++) {
            leaf[nowDigit] = poolTeam[i];
            makePI(leaf, nowDigit+1, targetDigit, poolTeam, indicator);
        }
    }


    // 메인
    public static void main(String[] args) throws Exception {
        // 입력부
        N = Integer.parseInt(input.readLine());
        origin = new int [N][N];
        for(int row =0; row<N; row++) {
            tokens = new StringTokenizer(input.readLine());
            for(int col =0; col<N; col++) {
                origin[row][col] = Integer.parseInt(tokens.nextToken());
            }
        }
//         세팅부
        team = new int[N/2];
        rival = new int[N/2];
        playerPool = new int[N+1];
        // 작업부
        makeCombi(team, 0, N/2, N, 1);

        // 출력부
        System.out.println(mini);
    }

}

퍼포먼스

[ 27,176 KB | 436 ms ]

마무리

조합과 중복순열을 연습하기에 좋은 문제다.

https://www.acmicpc.net/problem/13549

문제 소개 및 재정의

일차원 좌표 상의 N에서 K로 가능 최단 경로를 구하시오.

이동 방식과 비용

• +1,-1 이동에 1의 비용
• *2 이동에 0의 비용

문제 패턴

최단경로를 구하라 => BFS, Dijkstra ... 탐색 패턴은 익숙한 +1,-1과 그렇지 않은 *2 이동비용의 패턴이 단순해서 BFS로 풀 수 있을것 같다.

어떻게 풀까? - BFS

포인트

자잘한 포인트는 전체 코드의 주석에 있다.

처음에 수빈이의 위치와 시작시간 0초를 new int[] {N,0}의 형식으로 큐에 넣는다. 큐에서 하나씩 빼면서 각각의 이동패턴으로 이동한 위치와 소요시간을 큐에 넣어준다.

K에 도착하는데 걸리는 시간을 찾는것은 쉬운일이다. 하지만 처음에 찾은 시간이 무조건 최소값이 보장되는지를 판단하는게 어려웠다. 나중에 찾은 소요시간이 더 작을수도 있다고 생각돼서, 지금까지 찾은 최소 소요시간을 기준으로 큐의 확장을 억제하고. 큐에 남아있는 모든 경로의 소요시간도 확인했다.

큐를 확장 가능할때와 확장 불가능할때를 구분하는게 중요함

방문처리 안하면 +1 -1 +1 -1 이런식의 움직임으로 시간과 메모리가 터진다. 방문배열은 최대크기인 100_000에서 넉넉하게 *10을 해줬다. 좌표를 인덱스값으로 사용하는데 좌표가 범위인100_000을 넘어가기도 해서 그렇게 했다. 처음에는 방문 미방문만을 확인하기 위해서 boolean 타입의 배열로 선언했지만, 잘안됐다. 해당 좌표의 도착시간을 기록함으로써 더 나중에 도착한 값의 도착시간이 더 짧다면 새로이 방문할수 있도록 했다.

코드

// 이렇게 해서 틀리는 이유!!! 
// 소요시간이 더 늦은게 먼저 방문처리 해버리면, 소요시간이 더 빠른게 방문처리에서 필터링됨. 
// 따라서 방문처리는 참 거짓이 아니라, 도착한 시간을 기록해서 먼저 도착한 녀석을 기록해두고. 
// 도착시간을 비교해서 필터링 해야함.

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

public class BOJ_13549_숨바꼭질3_3 {
    // 입력고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;

    // 세팅
    static int N;
    static int K;
    static int miniTime = Integer.MAX_VALUE;
    static int[] visitTime; // 해당 좌표에 도착한 최단 시간을 기록함.

    // 메소드
    static void BFS() {
        // 초기화
        Queue<int[]> q = new LinkedList();
        q.offer(new int[] {N,0});

        // 돌아돌아 
        while(q.isEmpty() == false) {
            // 꺼냄
            int[] now = q.poll();
            int location = now[0];
            int time = now[1];

            // 확장할 필요 없는 큐 필터링
            //// 음수로 수렴하는것들은 불필요함. // location이 인덱스와도 연관돼있기 때문에 최상단에 위치해야함.
            if(location<0)
                continue;
            //// 최소 시간 이상인 값 버림.
            if(time>=miniTime) {
                continue;
            }
            // 이전에 방문한 최단시간보다 지금 도착한 시간이 더 빠르면 진행해야 하므로, 그 반대는 필터링
            if(visitTime[location]<=time) 
                continue;
            // 해당 좌표 최단시간 신기록 갱신
            visitTime[location]=time;
            //// K값 나올때 시간 저장. 이 시간보다 늦은건 필요 없음.
            if(location==K) {
                miniTime = Math.min(miniTime, time);
                continue; // 더 이상 확장 불필요
            }
            // K값을 넘겼을때는 내리는거만 작동시키기.(주로 *2로 계속 확장하는거 예외처리) 내리다가 시간초과하면 버려짐.
            else if(location>K) {
                q.offer(new int[] {location-1, time+1});
                continue;
            }
            // 예외처리 필요없는 것들
            else { // 0<= location <K
                q.offer(new int[] {location*2, time});
                q.offer(new int[] {location+1, time+1});
                q.offer(new int[] {location-1, time+1});
            }
        }
    }
    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        K = Integer.parseInt(tokens.nextToken());
        // 세팅
        visitTime = new int[100000*10];
        Arrays.fill(visitTime, Integer.MAX_VALUE);
        // 작업
        BFS();
        // 출력
        System.out.println(miniTime);
    }

}

퍼포먼스

[ 26,692 KB | 112 ms ]

마무리

방문 배열을 int 타입으로 선언하면 여러모로 다양한 로직이 가능해진다. 논리를 매핑하는게 성가셔서 boolean으로 쓰는 연습을 하고 있었는데. 거기에 집중하다 보니 int로 더 다양하게 쓰는 발상이 떠오르는 힘이 약해진것 같다.

https://www.acmicpc.net/problem/3079

문제 소개 및 재정의

M명의 사람이 N개의 창구에서 심사를 받는데 걸리는 최소 시간을 구하시오. 각각의 창구는 심사하는데 걸리는 시간이 다를수 있음.

문제 패턴

이전 이진탐색 포스트에서 정제한 패턴에 비춰보면. M개의 아이템 N개의 박스로 보여지기도 한다. 박스의 크기는 전체시간으로 결정된다. 그리고 입력의 크기가 심각하게 크다. 10억! 이진탐색으로 해결해야겠다는 생각이 먼저 들었다.

어떻게 풀까? - 시뮬레이션

시도에 대한 배경

그런데 빈 곳으로 바로 가지 않고, 끝나는 시간이 더 빠른 곳이 빌때까지 기다린다는 문제의 조건을 보고 이 점을 보장하는 방법을 생각하게 됐다. 다시 말하면, 심사를 했을떄 끝나는 시간이 더 빠른 곳에 간다는 것이다.

대기열 + 제일 먼저 끝나는 곳으로 간다는 점에서 우선순위 큐 그 자체라는 생각이 든다.

포인트

모든 입국 심사대를 우선순위 큐에 인큐한다. 입국 심사대는 심사를 한번 하는데 필요한 시간(loading) 과 지금 하고 있는 심사가 끝나는 시간(endTime)을 가진다. endTime에 대해서 정렬을 해두면 디큐할때마다 가장 빨리 끝나는 창구가 나오게 된다.

따라서 디큐가 가지는 의미는 한명이 심사를 끝냈다는 것과 그 창구에서 심사가 가능하다는 의미를 가진다. 따라서 디큐할때 심사를 한 사람의 수(peopleCount)를 세주고, 다시 해당 창구에서 심사를 시작하도록 endTime에 loading을 더해줘서 인큐한다.

이렇게하면 끝나는 시간이 빠른 순으로 입국심사대를 사용하게 된다. 따라서, 더 빠른 곳이 빌때까지 기다렸다 사용하는 것이 보장된다.

인큐와 디큐가 무한히 반복되는 구조이므로 peopleCount==M일때 탈출한다.

코드 - 우선순위 큐에 클래스를 인큐

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

public class BOJ_3079_입국심사 {
    // 입력 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    // 세팅
    static int N;
    static int M;
    // 메소드

    // 클래스
    static class Simsa implements Comparable<Simsa> {
        int loading;
        int endTime;

        Simsa(int loading, int endTime){
            this.loading = loading;
            this.endTime = endTime;
        }

        @Override
        public int compareTo(Simsa o) {
            return Integer.compare(this.endTime, o.endTime);
        }
    }

    // 메인
    public static void main(String[] args) throws Exception {

        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());

        PriorityQueue<Simsa> pq = new PriorityQueue<Simsa>();
        for(int i=0; i<N; i++) {
            int loading = Integer.parseInt(input.readLine());
            pq.offer(new Simsa(loading, loading));
        }
        // 세팅
        // 작업
        int peopleCount = 0;
        // 디큐할때마다 한명의 심사가 끝남. M명의 심사가 끝났을때 카운트는 M임. 디큐하고나서 카운트가 M이라면 해당 Simsa의 endTime을 값으로 제출.
        while(pq.isEmpty()==false) {
            Simsa nowEndSimsa = pq.poll(); 
            peopleCount++;
            int loading = nowEndSimsa.loading;
            int endTime = nowEndSimsa.endTime;
            pq.offer(new Simsa(loading, endTime+loading));
            if(peopleCount==M) {
                System.out.println(endTime);
                break;
            }
        }
        // 출력
    }
}

코드 - 우선순위 큐에 int[]를 인큐

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

public class BOJ_3079_입국심사2 {
    // 입력 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    // 세팅
    static int N;
    static int M;
    static int[] origin;
    // 메소드

    // 클래스
    static class Simsa implements Comparable<Simsa> {
        int loading;
        int endTime;

        Simsa(int loading, int endTime){
            this.loading = loading;
            this.endTime = endTime;
        }

        @Override
        public int compareTo(Simsa o) {
            return Integer.compare(this.endTime, o.endTime);
        }
    }

    // 메인
    public static void main(String[] args) throws Exception {

        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());

        origin = new int[N];
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
            Comparator.comparingInt(o->o[1])
        );

        for(int i=0; i<N; i++) {
            int loading = Integer.parseInt(input.readLine());
            pq.offer(new int[] {loading,loading});
        }
        // 세팅
        // 작업
        int peopleCount = 0;
        // 디큐할때마다 한명의 심사가 끝남. M명의 심사가 끝났을때 카운트는 M임. 디큐하고나서 카운트가 M이라면 해당 Simsa의 endTime을 값으로 제출.
        while(pq.isEmpty()==false) {
            int[] nowEndSimsa = pq.poll(); 
            peopleCount++;
            int loading = nowEndSimsa[0];
            int endTime = nowEndSimsa[1];
            pq.offer(new int[] {loading, endTime+loading});
            if(peopleCount==M) {
                System.out.println(endTime);
                break;
            }
        }
        // 출력
    }
}

한계

아니나 다를까 잘 안됐다! 이진 탐색 문제인데 그렇게 안 풀었으니까. 하지만 우선순위 큐에 미숙했던터라 우선순위 큐를 연습한 것에 만족했다.

공간 복잡도 사람수인 M의 크기가 O(10억)이기 때문에 10억개의 클래스를 만들어야 한다. Integer 두개로 구성된 클래스이기 때문에 단순하게 계산해봐도 다음과 같다. 8byte10억2 = 160억 byte => 대략 16GB의 메모리를 필요로 한다

시간 복잡도 디큐를 10억번 해야한다. 인큐는 10억번(디큐할때마다 인큐) + 10만번(우선순위 큐 초기화) 해야한다. (초기화 이후 디큐할때마다 인큐하므로) 따라서 대략 20억번의 우선순위 큐 업데이트가 발생한다. 우선순위 큐의 사이즈는 0부터 시작해서 10만에서 고정된다. 우선순위 큐를 1번 업데이트 하는데는 log2(10만) => 대략 16번의 연산이 필요하다. 따라서 20억*16==320억번의 연산이 필요하다. 연산량이 많다는 것은 그만큼 많은 정보를 가질수 있다는 뜻이다. O(M*log(N))

어떻게 풀까? - 이진 탐색

포인트

이진 탐색할 범위를 먼저 구해야한다. 0~아무 심사 시간*M 전체 시간은 양수이므로 범위는 0부터 시작한다. 어떤 창구라도 M번 심사하면 되므로 아무 심사 시간*M 까지다.

최악의 경우 모든 심사대의 심사시간이 10억(=10^9)이다. 그리고 심사 받아야하는 사람의 수도 10억이다. 이 경우 전체 시간은 10^18이다. 10^3은 대략적으로 2^10이므로 10^18은 2^60이 된다. 따라서 전체 시간과 관련된 변수를 int타입으로 저장하면 오버플로우가 발생한다. 그래서 long타입으로 저장돼야 한다. long타입도 2^63-1의 자연수까지만 표현가능해서 제법 꽉 찬다.

탐색 범위의 중앙값인 mid 시간내에 M명의 입국심사가 가능한지 확인한다. 가능하다면 시간을 줄여보기 위해서 탐색범위를 시작~중앙값-1로 결정한다. (성공했을때 성공한 값인 mid를 저장해둠으로써 최적값을 관리한다.) 불가능하다면 시간을 늘려봐야 하므로 탐색범위를 중앙값+1~끝 으로 결정한다.

코드 - 이진 탐색

static void bs(long start, long end) {
    // 바닥 조건
    if(start>end)
        return;

    // 재귀 파트
    long mid = (start+end)/2;
    if(isOK(mid)) {
        best = mid; // 성공할때마다 저장. 가장 최신 성공의 값으로 갱신됨. 최소값 유지.
        bs(start, mid-1);
    }else {
        bs(mid+1,end);
    }
}

코드 - 탐색 방향 결정 로직

static boolean isOK(long mid) {
    long sum =0;
    for(int i=0; i<N; i++) {
        sum += mid/origin[i]; // 정해진 시간(mid)동안 각각의 입국심사대가 처리할수 있는 사람의 수. 그것들의 합. // mid/origin[i]이 맞는데... origin[i]/mid 이따구로 해놨음.
    }
    if(sum>=M) // mid 시간동안 M명 이상을 처리할수 있음. ==> mid를 줄여보자
        return true;
    else // sum<M ==> mid 시간동안 M명을 처리할 수 없음. ==> mid를 늘려보자
        return false;
}

한계

논리적으로 완벽한데 자꾸 답이 안 나와서 힘들었다. 범위를 심사시간 최대값*M으로 하면 채점이 더 되고. origin을 정렬해두면 채점이 더 되고. 논리적으로 결론의 방향이 일정하지 않아서 아주 많이 헤맸다. 일단 논리적으로는 문제가 없다고 판단하여 다른 사람의 코드와 비교하면서 다른 점을 분석했다.

같은 자바를 사용한 풀이 코드도 나와 같은 타이밍에서 막혔다. 테스트 케이스가 추가된듯하다. 파이썬 풀이 코드와 비교해봤다. 완전히 똑같은 로직인데, 파이썬 코드는 통과했다. 자바혐오를 멈춰주세요 ㅠ 자바와 파이썬의 다른점이 키포인트일것으로만 추정된다.

해당 문제의 질문게시판에서 나와 같은 증상을 호소하는 사람을 봤고 그곳에 정답이 있었다. https://www.acmicpc.net/board/view/141496

심사가 끝난 사람을 구하는 과정에서 이미 M을 넘겼으면 더 이상 더하지 않고 끝내야 안전하다. 최악의 경우를 가정해보자. 하나의 심사대가 10억의 시간을 소모하고 나머지는 1을 소모한다. 심사를 받아야 하는 사람의 수는 10억명이다. 탐색범위는 (0~10^18)가 된다. 처음에 들어오는 mid의 값은 (10^18)/2다. 심사가 끝난 사람 수인 mid/각 심사대 소요시간을 더하게되면 (10^18)/2를 (10억-1)번 더하게 된다. 그 값이 (10^27)/2 ==> 2^(90-1)에 육박한다. 따라서 long에서도 오버플로우가 발생한다.

그것을 막기 위해서 M을 넘겼을때 더 이상 더하지 않도록 반복문을 조기 종료하는 방법이 있다. (M을 넘겼을때 우리가 필요한 정보는 이미 획득된 상태이므로) 한번에 최대로 더할수 있는 값은 (10^18)/2이다. 두번 더하더라도 (10^18)으로 오버플로우가 발생하지 않는 값이다. M은 10^9가 최대이므로, M을 넘긴 상태에서 최대값이 들어오더라도 오버플로우는 발생하지 않는다.

코드 - 탐색 방향 결정 로직 (수정됨)

static boolean isOK(long mid) {
    long sum =0;
    for(int i=0; i<N; i++) {
        if(sum>=M) 
            break;
        sum += mid/origin[i]; // 정해진 시간(mid)동안 각각의 입국심사대가 처리할수 있는 사람의 수. 그것들의 합. // mid/origin[i]이 맞는데... origin[i]/mid 이따구로 해놨음.
    }
    if(sum>=M) // mid 시간동안 M명 이상을 처리할수 있음. ==> mid를 줄여보자
        return true;
    else // sum<M ==> mid 시간동안 M명을 처리할 수 없음. ==> mid를 늘려보자
        return false;
}

전체 코드

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

public class BOJ_3079_입국심사4 {
    // 입력 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    // 세팅
    static int N;
    static int M;
    static int[] origin;
    static long best;
    // 메소드
    //// 이진탐색
    static void bs(long start, long end) {
        // 바닥 조건
        if(start>end)
            return;

        // 재귀 파트
        long mid = (start+end)/2;
        if(isOK(mid)) {
            best = mid; // 성공할때마다 저장. 가장 최신 성공의 값으로 갱신됨. 최소값 유지.
            bs(start, mid-1);
        }else {
            bs(mid+1,end);
        }
    }

    //// 탐색 방향 결정 로직
    static boolean isOK(long mid) {
        long sum =0;
        for(int i=0; i<N; i++) {
            if(sum>=M) 
                break;
            sum += mid/origin[i]; // 정해진 시간(mid)동안 각각의 입국심사대가 처리할수 있는 사람의 수. 그것들의 합. // mid/origin[i]이 맞는데... origin[i]/mid 이따구로 해놨음.
        }
        if(sum>=M) // mid 시간동안 M명 이상을 처리할수 있음. ==> mid를 줄여보자
            return true;
        else // sum<M ==> mid 시간동안 M명을 처리할 수 없음. ==> mid를 늘려보자
            return false;
    }


    // 메인
    public static void main(String[] args) throws Exception {

        // 입력
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());

        origin = new int[N];
        for(int i=0; i<N; i++) {
            origin[i] = Integer.parseInt(input.readLine());
        }
        // 세팅
        // 작업
        bs((long) 0, (long) origin[0]*M); // 아무 입국심사대에서나 M번처리하면 모두 처리 가능하므로 끝값을 그렇게 설정.
        // 출력
        System.out.println(best);
    }
}

퍼포먼스

[ 22_508 KB | 252 ms ]

마무리

이 캐릭터는 수를 더할때 꼭 오버플로우를 생각하는 직업병이 추가되었습니다.

https://www.acmicpc.net/problem/2512

문제 소개 및 재정의

총 예산 M이 주어졌을때 N개의 예산요청을 처리할수 있는 예산 상한액 K를 찾으시오. K중에서 N개의 예산요청 처리후 집행하는 총 예산이 M과 가장 가깝게 하는 K를 구하시오.

예산 집행 규칙. K이하의 예산요청(smaller)은 smaller의 값을 그대로 집행. K를 초과하는 예상요청(bigger)는 예산 상한액인 K의 값으로 집행.

문제 패턴

고정된 크기 K에 N개의 아이템을 넣어야 할때 최적의 K값을 찾으시오. => 이진 탐색

O(K*N) = 10^9 = 10억 일때 => 아주 큰 규모 => 이진 탐색

어떻게 풀까? - 이진 탐색

포인트

먼저 이진탐색을 구현하고, 탐색 방향을 결정할 로직을 결정한다.

탐색 방향 결정할 로직 구현 후 어떤 방향에 매핑해야 될지 잘 모르겠다면, BruteForce하게 대입해봐도 괜찮다. true - false false - true 대입 후 프린트를 찍어보면 문제를 더 빠르고 정확하게 풀 수 있다.

정확도와 안정성이 중요한 작업이라면 신중하게 한번에 정답을 찾아야 하겠지만, 시험볼때는 위의 것들과 더불어 속도가 생명이다. BruteForce를 사용할 수 있는 환경이라면 과감하게 사용하자. 대부분의 연구는 실험 결과를 토대로 가설을 검증한다. 그런면에서 나쁘지 않은 방법이다.

코드

이진 탐색

//// 이진탐색
static void bs(int start, int end) {
    // 바닥 조건
    if(start>end)
        return;
    // 재귀 파트
    int mid = (start+end)/2;
    if(isOK(mid)) {
        bs(start,mid-1);
    } else {
        best = mid;
        bs(mid+1,end);
    }
}

탐색 방향 결정 로직

static boolean isOK(int mid) {
    int sum = 0;
    for(int i=0; i<N; i++) {
        if(origin[i]<=mid)
            sum+=origin[i];
        else  //origin[i]>mid
            sum+=mid;
    }
    // 순회 종료
    if(sum<=M) { // 예산승인 가능. 예산 상한액 증감 가능.
        return false;
    } else { // sum>M ==> 예산 초과됨. 예산 상한액 삭감
        return true;
    }
}

전체코드 - 정렬 버전

보통 이진탐색하면 아이템이 정렬되어야 하는 경우가 많다. 따라서 일단 정렬시키고 문제를 풀어보았다. 이 경우 장점

• 생각할게 적어진다.
• 이진탐색범위의 끝값을 찾기 위해서 MAX값을 찾아야 하는데 정렬하면 손쉽게 찾을수 있다. 코드 라인 감소

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

public class BOJ_2512_예산 {

    // 입력 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder outpur = new StringBuilder();

    // 세팅
    static int N;
    static int[] origin;
    static int M;
    static int best;


    // 메소드
    //// 이진탐색
    static void bs(int start, int end) {
        // 바닥 조건
        if(start>end)
            return;
        // 재귀 파트
        int mid = (start+end)/2;
        if(isOK(mid)) {
            bs(start,mid-1);
        } else {
            best = mid;
            bs(mid+1,end);
        }
    }

    static boolean isOK(int mid) {
        int sum = 0;
        for(int i=0; i<N; i++) {
            if(origin[i]<=mid)
                sum+=origin[i];
            else  //origin[i]>mid
                sum+=mid;
        }
        // 순회 종료
        if(sum<=M) { // 예산승인 가능. 예산 상한액 증감 가능.
            return false;
        } else { // sum>M ==> 예산 초과됨. 예산 상한액 삭감
            return true;
        }
    }

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        N = Integer.parseInt(input.readLine());
        origin = new int[N];
        tokens = new StringTokenizer(input.readLine());
        for(int i=0; i<N; i++) {
            origin[i] = Integer.parseInt(tokens.nextToken());
        }
        M = Integer.parseInt(input.readLine());

        // 세팅
        Arrays.sort(origin);
        // 작업
        bs(0,origin[N-1]);
        // 출력
        System.out.println(best);
    } // 메인 종료

}

전체 코드 - 정렬 안한 버전

하나의 박스에 여러개의 아이템을 넣는 경우가 있을 경우 고정된 순서로 정렬이여야 하거나, 아니면 오름차순으로 정렬이여야 한다.

하지만 이 문제처럼 하나의 박스에 1개의 아이템만 들어가는 경우에는 순서는 고려대상이 아니다. 하나의 박스에 하나의 아이템이 들어갈수 있냐 아니냐만 고려대상이기 때문이다.

문제해결 후 리뷰중, 정렬할 필요가 없다는 사실을 깨닫고 정렬없이 푼 버전이다. 범위를 지정하기 위해 max값을 별도로 찾아야 할 필요가 있었다. 코드상에서 차이는 딱 그거 하나다.

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

public class BOJ_2512_예산 {

    // 입력 고정
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder outpur = new StringBuilder();

    // 세팅
    static int N;
    static int[] origin;
    static int M;
    static int best;


    // 메소드
    //// 이진탐색
    static void bs(int start, int end) {
        // 바닥 조건
        if(start>end)
            return;
        // 재귀 파트
        int mid = (start+end)/2;
        if(isOK(mid)) {
            bs(start,mid-1);
        } else {
            best = mid;
            bs(mid+1,end);
        }
    }

    static boolean isOK(int mid) {
        int sum = 0;
        for(int i=0; i<N; i++) {
            if(origin[i]<=mid)
                sum+=origin[i];
            else  //origin[i]>mid
                sum+=mid;
        }
        // 순회 종료
        if(sum<=M) { // 예산승인 가능. 예산 상한액 증감 가능.
            return false;
        } else { // sum>M ==> 예산 초과됨. 예산 상한액 삭감
            return true;
        }
    }

    // 메인
    public static void main(String[] args) throws Exception {
        // 입력
        N = Integer.parseInt(input.readLine());
        origin = new int[N];
        tokens = new StringTokenizer(input.readLine());
        int max = 0;
        for(int i=0; i<N; i++) {
            origin[i] = Integer.parseInt(tokens.nextToken());
            max = Math.max(max, origin[i]);
        }
        M = Integer.parseInt(input.readLine());

        // 세팅
        // 작업
        bs(0,max);
        // 출력
        System.out.println(best);
    } // 메인 종료
}

퍼포먼스

정렬 버전 [ 14_104 KB | 108 ms ]

정렬X 버전 [ 13_076 KB | 92 ms ]

퍼포먼스에서 유의미한 차이는 안 보인다.

마무리

BruteForc한 시도를 할 수 있는 환경이라면 꼭 하자!