GOSE_KOSE

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 문자열 문제 - 비밀번호 발음하기 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/4659

1. 풀이 소스

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String str = "";
        
        boolean isPossible; // 가능한 경우 판단 
        boolean flag; // 모음 중 하나는 반드시 포함 
        boolean isVowelSeq; // 모음이 연속인지 ?
        int seq; // 모음 연속 
        char pre; // 이전 문자열 
        
        while ((str = br.readLine()) != null && !str.equals("end")) {
            pre = str.charAt(0);
            seq = 0;
            flag = isVowelSeq = false;
            isPossible = true;
            
            if (str.length() >= 1) { // 문자열이 1개 이상인 경우 pre 설정, flag = true
                if (pre == 'a' || pre == 'e' || pre == 'i' || pre == 'o' || pre =='u') {
                    flag = true;
                    isVowelSeq = true; // 모음인 경우 true, 자음인 경우 false
                } 
                seq++; // seq 증가                    
            }
            
            for (int i = 1; i < str.length(); i++) {
                char c = str.charAt(i);
                
                if (!flag && (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c =='u')) flag = true; // 아직 모음 판단 안한 경우
                
                if (pre == c) { // 3번 같은 글자 연속 두번 불가
                    if (!(pre == 'e' || pre == 'o')) {
                        isPossible = false; // 불가능한 경우 종료
                        break;
                    }
                }
                
                // 2번 판단 
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c =='u') {
                    if (isVowelSeq) seq++; // 모음 seq 증가 
                    else { // 이전이 자음이었다면
                        isVowelSeq = true;
                        seq = 1;
                    }
                } else { // 자음이라면
                    if (isVowelSeq) { // 이전이 모음이었다면
                        isVowelSeq = false;
                        seq = 1;
                    } else seq++; // 이전에도 자음이었으므로 seq 증가
                }
                
                if (seq >= 3) { 
                    isPossible = false;
                    break;
                }

                pre = c;
            }
            
            if (flag && isPossible) {
                sb.append("<").append(str).append("> is acceptable.").append("\n");
            } else {
                sb.append("<").append(str).append("> is not acceptable.").append("\n");
            }
        }
        
        System.out.print(sb);
    }
}

2. 풀이 중점 사항

주어진 3가지 조건을 만족하는 코드를 작성하기 위해 flag, isVowelSeq 등의 boolean 변수를 선언하였습니다.

자음과 모음에 대한 seq를 따로 설정하지 않아도 boolean 변수로 모음은 true, 자음은 false로 설정하여 seq를 한 번에 관리할 수 있었습니다.

자세한 코드는 주석처리 하였습니다. 감사합니다!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅에 앞서, 최근에 제가 가고 싶었던 회사의 코딩테스트가 있었습니다.

준비를 안 한 것은 아니지만, 부족했고 정말 기본이라고 할 수 있는 문자열 문제에서 고생을 해서, 많은 자괴감이 들었습니다.

문자열에 대해서 다시 정리할 필요성을 느끼게 되어서 문자열 문제를 다시 풀어보았습니다.

문제 출처: https://www.acmicpc.net/problem/6550

1. 풀이 소스 

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

public class Main {
    
    static Queue<Character> queue = new ArrayDeque<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        String str;
        String target;
        String seq;
        StringTokenizer st;
        
        while ((str = br.readLine()) != null && !str.equals("EOF")) { // 종료 조건은 문자열이 null이 아니고 EOF가 아니여야 함
            st = new StringTokenizer(str);
            target = st.nextToken();
            seq = st.nextToken();
            
            for (int i = 0; i < target.length(); i++) {
                queue.add(target.charAt(i)); // 큐에 target 문자열 넣기
            }
            
            for (int i = 0; i < seq.length(); i++) {
                if (queue.isEmpty()) break; // seq를 순회하며 target을 넣은 queue가 비면 종료
                if (queue.peek() == seq.charAt(i)) { // 만약 큐에 있는 문자열과 seq 문자열이 같다면 큐에서 빼기
                    queue.poll();
                }
            }

            if (queue.isEmpty()) { // 큐가 비어있다면 부분 문자열임을 의미 
                sb.append("Yes").append("\n");
            } else {
                while(!queue.isEmpty()) { // 큐를 다시 비워주기 
                    queue.poll();
                }
                sb.append("No").append("\n");
            }
        }
        
        System.out.print(sb);
    }
}

2. 풀이 중점 사항

종료 조건으로 str = br.readLine() && !str.equals("EOF")를 토대로 종료 조건을 처리해주어야 합니다.

부분 문자열을 구성하기 위해 queue를 이용하여 문자열을 담은 후, 큐에서 하나씩 빼며 문자열을 처리하도록 하였습니다

이상으로 백준 부분 문자열 문제 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 투포인터 문제 부분합 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/1806

1. 풀이 소스

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

import static java.lang.Integer.parseInt;

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

        int n = parseInt(st.nextToken());
        int s = parseInt(st.nextToken());
        PartialSum ps = new PartialSum(n, s);

        st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < n; i++) {
            ps.setMap(i, parseInt(st.nextToken()));
        }

        ps.run();
        System.out.println(ps.getResult());
    }
}

class PartialSum {
    int n;
    int target;
    int result = Integer.MAX_VALUE;
    int[] map;

    public PartialSum(int n, int target) {
        this.n = n;
        this.target = target;
        map = new int[n + 1];
    }

    void setMap(int i, int value) {
        map[i] = value;
    }

    void run() {
        int length = 0;
        int sum = 0;
        int left = 0;
        int right = 0; 

        while (left <= n && right <= n) {
            if (sum < target) { // 타겟이 더 큰 경우
                sum += map[right++]; // 값을 더한 후, 오른쪽 포인터 한 칸 증가  
            } else {
                sum -= map[left++]; // 현재 있는 값 빼고 왼쪽 포인터 한 칸 증가  
                length = right - left + 1; 
                result = Math.min(length, result);
            }
        }
    }

    int getResult() {
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

// 순서
// 포인터에 위치한 값을 처리하고 포인터 이동
// sum이 target보다 크거나 같다면,
// sum에서 left포인트 값 빼고, left 이동 시킴
// 그 후 right - left한 후 + 1 (개수 이므로)

// sum이 target보다 작다면
// sum에서 right값을 더하고 포인터 이동

// 0 1 2 3 4
// 0     0
//

// target = 3
// p: 1, 3,  sum : 1 + 2
// p: 2, 3   sum : 2    --> length = 3 - 2 + 1
// p: 2, 3 sum(2)

2. 풀이 중점 사항

자연수로된 부분합 문제의 큰 특징은 단조 증가라는 것입니다.

예를 들어, 1, 3, 5, 3, 7 이 있을 때,

시작 수열의 인덱스가 1이고, 끝 인덱스가 3이라고 가정하겠습니다.

그렇다면 합은 3, 5, 3 이 됩니다.

여기서 합을 늘리는 방법은 두가지가 있습니다.

시작 인덱스를 -- 하거나, 끝 인덱스를 ++ 하는 방법입니다.

만약 합 12를 만족하는 가장 짧은 연속된 수열을 선택하는 경우가 생긴다면 다음과 같이 선택할 수 있습니다.

5, 3, 7 입니다.

투포인터를 활용한다면

1 

s

e                      (12 보다 작으므로 e 포인터 1 증가)

1    3

s    e                (12 보다 작으므로 e 포인터 1 증가)

1    3    5

s          e            (12 보다 작으므로 e 포인터 1 증가)

1    3    5    3

s                 e     (12를 만족하므로 s포인터를 1 증가)

3    5    3

s           e         (12 보다 작으므로 e 포인터 1 증가, s를 감소시키지 않은 이유는 이전에 s가 1일 때를 이미 했으므로 (무한 루프 방지))

3    5    3    7

s                e    (12를 만족하므로 포인터 s 1 증가)

5       3       7

s                e   (12를 만족하므로 포인터 s 1 증가)

3       7 

s       e          (12 보다 작으므로 e 포인터 1 증가 --> 인덱스 끝이므로 더 이상 단조 증가 불가 -> 종료)

처럼 해결할 수 있습니다.

while (left <= n && right <= n) {
    if (sum < target) { // 타겟이 더 큰 경우
        sum += map[right++]; // 값을 더한 후, 오른쪽 포인터 한 칸 증가
    } else {
        sum -= map[left++]; // 현재 있는 값 빼고 왼쪽 포인터 한 칸 증가
        length = right - left + 1;
        result = Math.min(length, result);
    }
}

따라서, 만약 타깃보다 값이 작다면 right를 증가시키고,

타깃보다 값이 같거나 크다면 left를 증가시키는 방법으로 문제를 해결할 수 있습니다.

이상으로 투포인터 부분합 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 투포인터 문제 - 두 수의 합 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/3273

1. 풀이 소스

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());

        TwoSum ts = new TwoSum(n);
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            ts.setMap(i, parseInt(st.nextToken()));
        }
        ts.setSum(parseInt(br.readLine()));
        ts.run();
        System.out.println(ts.getPair());;
    }
}

class TwoSum {

    int n; // n개의 입력
    int[] map; // 입력 배열
    int target; // 목표 합
    int pair; // 순서쌍 개수

    public TwoSum(int n) {
        this.n = n;
        map = new int[n];
    }

    void setMap(int i, int value) {
        map[i] = value;
    }

    void run() {
        Arrays.sort(map); // 오름차순 정렬하여 투포인터가 가능하도록 설정
        if (map.length == 1) return; // n이 하나인 경우 불가

        int left = 0; // 시작점
        int right = n - 1; // 끝 점

        while(left < right) { // 두 좌표가 교차된다면 종료 (left -> right, right -> left는 두 참조 이름만 바뀐 것이기 때문)

            int value = map[left] + map[right];

            if (target > value) left++; // 만약 목표보다 값이 작다면 left를 증가시켜서 합이 커지도록
            else if (target < value) right--; // 목표보다 크다면 right를 줄여서 합이 작아지도록
            else {
                pair++;
                left++; // left를 증가시켜서 무한루프를 막고 시작점을 현재 인덱스 다음으로 넘겨줌
            }
        }
    }

    void setSum(int target) {
        this.target = target;
    }

    int getPair() {
        return pair;
    }
}

2. 풀이 중점 사항 

일반적으로 두 수의 합 순서쌍을 구하는 경우는 이중 포문으로 구성하면 빅오 n^2이 나옵니다.

투포인터를 활용한다면 빅오 n으로 문제를 해결할 수 있습니다. 

오름차순 된 배열의 각 양 끝점을 포인터로 설정하고, 

목표로 하는 값 K보다 값이 작다면, left 포인터를 증가시킵니다.

배열은 오름차순 되어있기 때문에 1, 2, 3, 4, 5처럼 인덱스가 커질수록 단조 증가처리 됩니다.

따라서, 목표로 하는 값보다 작으므로 left를 증가시켜서 값을 늘리고,

늘렸더니 값이 다시 커진다면, right를 감소시켜서 값을 줄이는 방법입니다.

이러한 과정을 통해 원하는 k에 수렵하는 포인터 쌍을 구할 수 있습니다.

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 

이번 포스팅은 백준 DP문제 - 상자넣기 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1965

1. 풀이 소스

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        Box box = new Box(n);

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            box.setMap(i, parseInt(st.nextToken()));
        }

        box.run();
        System.out.println(box.getResult());
    }

}

class Box {
    int n;
    int[] map; // 값 저장
    int[] dp; // 최대 몇개를 넣을 수 있는지 저장하는 DP
    int result;
    public Box(int n) {
        this.n = n;
        map = new int[n];
        dp = new int[n];
    }

    public void setMap(int i, int value) {
        map[i] = value; // 0: 값
    }

    int getResult() {
        return result;
    }

    public void run() {
        dp[0] = 1; // 첫 번째 선택은 1

        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (map[j] < map[i]) { // 만약 현재 있는 상자의 값보다 적다면
                    dp[i] = Math.max(dp[j], dp[i]); // 그 적은 상자와 현재 dp를 비교하여 업데이트
                }
            }
            dp[i] += 1; // 자기 자신을 넣어야 하므로 +1
            result = Math.max(dp[i], result);
        }
    }
}

2. 풀이 중점 사항

현재 A라는 위치에 있는 상자를 기준으로 가장 많이 넣을 수 있는 경우를 판단하려면 

1 2 3 ~ A - 1까지 상자를 순회하며 몇 개의 상자를 넣을 수 있는지 판단해야 합니다. 

만약 1 5 3 7 이라는 상태가 주어졌고,

7에 넣을 수 있는 상자를 판단하려면 

1 , 5 넣거나 안넣거나, 만약 5가 있다면 3 X, 5가 없다면 3 O 이러한 식으로 복잡한 구성이 되어야 합니다.

이러한 문제를 해결하기 위한 방법이 DP를 활용하는 것입니다.

dp[0] = 1; // 첫 번째 선택은 1

먼저, 0번째 인덱스, 즉 첫 번째 원소를 상자에 넣어서 값이 최대가 되는 방법은 무조건 자기 자신을 넣는 것입니다.(자기 자신과 크기가 같은 상자가 있으므로)

for (int i = 1; i < n; i++) {
    for (int j = i - 1; j >= 0; j--) {
        if (map[j] < map[i]) { // 만약 현재 있는 상자의 값보다 적다면
            dp[i] = Math.max(dp[j], dp[i]); // 그 적은 상자와 현재 dp를 비교하여 업데이트
        }
    }
    dp[i] += 1; // 자기 자신을 넣어야 하므로 +1
    result = Math.max(dp[i], result);
}

map은 값을 저장하는 배열입니다. 1 5 3 7 을 map에 각각 인덱스에 맞게 넣는 것입니다.

dp는 각 인덱스에 최대 몇 개를 넣을 수 있는지를 판단하는 것입니다.

map과 dp를 함께 보면, map[i]에 있는 값을 가진 상자에 최대 몇 개의 상자를 넣을 수 있는지를 dp[i]에 기록하는 것입니다.

5 => index 1이므로,

if (map[0] < map[1]) :

    dp[i] = Math.max(dp[0], dp[1]) 

dp[i] += 1

이전 dp의 최대이면서, 자기 자신보다 값이 작은 상자를 골라 하나를 더해주는 로직을 완성할 수 있습니다.

이상으로 상자넣기 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP문제 - 합분해 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2225

1. 풀이 소스

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());
        
        SumDivision sd = new SumDivision(n, k);
        sd.run();
    }
}

class SumDivision {
    
    static final int MOD = 1000000000;
    int n;
    int k;
    int[][] dp;

    SumDivision(int n, int k) {
        this.n = n;
        this.k = k;
        dp = new int[k + 1][n + 1]; // i 개로 총 합이 j을 만드는 것        
    }
    
    void run() {

        Arrays.fill(dp[1], 1); // i = 1, 즉 1개로 j의 값을 만드는 경우는 한 개
        for (int i = 1; i <= k; i++) dp[i][0] = 1; // 총 합이 0이 되도록 만드는 경우는 각 개수 별로 한 개씩 
        // ex) i = 1, 합이 0 ==> 0 (한 개 존재)
        // ex) i = 2, 합이 0 ==> 0 + 0 (한 개 존재)

        // dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + .... + dp[i - 1][j];
        //   j
        // = sum(dp[a - 1][b]) 
        //   b -> 0 

        //   j - 1
        // = sum(dp[a - 1][b]) + dp[i - 1][j]
        //   b -> 0

        // = dp[i][j - 1] + dp[i - 1][j]
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                dp[i][j] %= MOD;
            }
        }

        System.out.println(dp[k][n]);
    }
}

2. 풀이 중점 사항

이번 문제는 점화식을 도출하는 과정이 많이 어려웠습니다.

정수 K개를 더해서 N까지의 합을 어떻게 만들어야 하는가가 핵심이었습니다.

하나의 예시를 살펴보겠습니다.

N을 만들기 위해서는 합이 0 ~ n 이 되도록 k - 1개를 사용하여야 합니다.

즉, N이 3이라면

k = 2일 때, preSum = 0, 1, 2, 3 이 완성되어야 합니다.

k = 3이라면,

preSum = 0     +      3 (현재)

preSum = 1     +      2 (현재)

preSum = 2     +      1 (현재)

preSum = 3     +      0 (현재)

를 구할 수 있습니다. 이를 수학적으로 표현하면 다음과 같습니다.

DP[a][b]가 a개를 사용하여 값이 b를 만드는 경우의 수라고 한다면,

DP[k][N] =  DP[k - 1][0] + DP[k - 1][1] +    ...   + DP[k - 1][N] 으로 표현할 수 있습니다.

하단에 참조 블로그의 블로거 분께서 점화식을 도출해주셨는데, 참고하면 다음과 같습니다.

시그마의 성질로 인해 마지막 항을 따로 분리하면, dp[K - 1][N]이 되고, 시그마를 정리하면 dp[k][N - 1]이 되므로 두 항을 더하면

하나의 점화식을 완성 시킬 수 있습니다.

dp[i][j] = dp[i][j - 1] + dp[i - 1][j];

이때, k = 1으로 N을 만드는 경우의 수는 자기 자신을 더하는 것밖에 없으므로 

dp[1][all] = 1 을 처리해주어야 합니다. 또한, k개로 0을 만드는 경우도 마찬가지로 1 개입니다.

ex) k = 1 -> 0

      k = 2 -> 0 + 0

따라서, 이 경우들을 제외하고는 위의 점화식을 적용시키면 문제를 해결할 수 있습니다.

이상으로 백준 합분해 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

참고 자료: https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-2225-%EC%9E%90%EB%B0%94-%ED%95%A9%EB%B6%84%ED%95%B4-BOJ-2225-JAVA

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP문제 점프 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1890

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        
        Jump jump = new Jump(n);
        for (int row = 0; row < n; row++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int col = 0; col < n; col++)
                jump.setMap(row, col, parseInt(st.nextToken()));
        }
        
        jump.run();
        System.out.println(jump.getPath());
    }
}

class Jump {
    int n;
    int[][] map; // 점프 값 저장
    long[][] dp; // 점프 후 dp 저장 2^63 - 1까지 저장 될 수 있으므로
    
    Jump (int n) {
        this.n = n;
        map = new int[n][n];
        dp = new long[n][n];
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value; // 좌표에 맞는 값 설정하기
    }
    
    void run() {
        dp[0][0] = 1; // 초기 값 설정

        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {

                int d = map[row][col];
                if (d == 0) continue; // 만약 이동 거리가 0이라면 중복 저장을 막기 위함 dp[row][col + 0] += dp[row][col] 방지

                if (isValid(row, col + d)) { // 값만큼 열 점프
                    dp[row][col + d] += dp[row][col];
                }

                if (isValid(row + d, col)) { // 값만큼 행 점프
                    dp[row + d][col] += dp[row][col];
                }
            }
        }
    }
    
    boolean isValid(int row, int col) { // 유효한 인덱스
        return row >= 0 && row < n && col >= 0 && col < n;
    }

    long getPath() { // 마지막 0의 종료점 좌표
        return dp[n - 1][n - 1];
    }

}

2. 풀이 중점 사항

DP로 해결하므로 빅오(n^2) = (100 * 100)으로 문제를 해결할 수 있습니다.

중점 사항은 d == 0이 될 때, += 의 성질로 인해 같은 값이 중복 저장될 수 있습니다.

따라서, map[row][col] == 0이라면 해당 로직은 건너뛰어서, 값의 중복 저장을 막아야 합니다.

자세한 풀이는 주석화 하였습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP문제 - 동전 2 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/2294

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());
        Coin coin = new Coin(n, k);
        
        for (int i = 0; i < n; i++) {
            coin.setCoin(parseInt(br.readLine()));
        }
        
        coin.run();
        System.out.println(coin.getResult());
    }
}

class Coin {
    int n;
    int k;
    int[] dp; // 각 인덱스에 들어갈 값은 코인의 최소 개수
    int result; // 결과 저장 
    List<Integer> coins = new ArrayList<>(); // 코인 값 저장 
    
    Coin (int n, int k) {
        this.n = n;
        this.k = k;
        dp = new int[k + 1]; 
        Arrays.fill(dp, Integer.MAX_VALUE); // 모두 최고값으로 초기화
    }
    
    void setCoin(int won) {
        coins.add(won);
    }
    
    void run() {
        
        dp[0] = 0; // 0을 만드는 경우는 0개임
        for (int i = 1; i <= k; i++) {
            for (Integer coin : coins) {
                if (i - coin < 0 || dp[i - coin] == Integer.MAX_VALUE) continue; // 만약 인덱스가 0 미만이거나, 만들 수 없는 값인 경우
                dp[i] = Math.min(dp[i - coin] + 1, dp[i]); // 코인의 값을 인덱스로 뺀다면 그 값이 설정   
            }
        }
        
        if (dp[k] == Integer.MAX_VALUE) result = -1;
        else result = dp[k];
    }
    
    int getResult() {
        return result;
    }
    
}

2. 풀이 중점 사항

Memozation을 사용할 DP를 금액으로 설정하고 문제를 해결하였습니다.

각 동전은 coin이라는 리스트에 저장한 후,

1 ~ k까지 (각 경계 포함) for문을 돌리되, 각 코인을 내부에서 순환합니다. (빅오 n^2)

dp[i] = Math.min(dp[i - coin] + 1, dp[i]); // 코인의 값을 인덱스로 뺀다면 그 값이 설정

dp[i - coin]은 dp는 금액을 메모한 배열이므로 i - coin은 i - coin 금액에 있는 동전 최소 개수가 됩니다.

즉, 동전이 500이고, 현재 i = 700일 때, dp[200]에서 500원 동전 한 개만 더해주면 700을 만들 수 있는 원리입니다.

따라서 다음의 점화식을 작성하여 문제를 해결할 수 있었습니다.

이상으로 DP 동전 2 문제 풀이를 마치도록 하겠습니다. 감사합니다.!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP 문제 모음 스티커 자바 풀이를 진행하고자 합니다.

문제출처: https://www.acmicpc.net/problem/9465

1. 풀이 소스

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = parseInt(br.readLine());

        Sticker sticker = new Sticker();
        for (int i = 0; i < t; i++) {
            int n = parseInt(br.readLine());
            sticker.setInit(n);
            for (int row = 0; row < 2; row++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int col = 1 ; col <= n; col++)
                    sticker.setMap(row, col, parseInt(st.nextToken()));
            }
            sticker.run();
        }

        sticker.printResult();

    }    
}

class Sticker {
    int n;
    int[][] dp;
    int[][] map;
    List<Integer> result = new ArrayList<>();
    
    Sticker () {
    }

    void setInit(int n) {
        this.n = n;
        dp = new int[2][n + 1]; // dp를 담을 2차원 배열 
        map = new int[2][n + 1]; // 각 스티커의 값
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value; 
    }
    
    void run() {
        dp[0][1] = map[0][1]; // i가 2부터이므로 1을 초기화 
        dp[1][1] = map[1][1];
        
        for (int i = 2; i <= n; i++) {
            dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + map[0][i];
            dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + map[1][i];
        }
        result.add(Math.max(dp[0][n], dp[1][n]));
    }

    void printResult() {
        StringBuilder sb = new StringBuilder();

        for (Integer r : result) {
            sb.append(r).append("\n");
        }
        System.out.print(sb);
    }
}

2. 풀이 중점 사항

평소 DP가 약하여, 점화식을 도출하는 것에서 바로 떠오르지 않아 이러한 형태의 문제에서는 자동적으로 

현재 DP = Math.max(이전 DP, 이전*2 DP)를 적어놓고 문제를 다시 보곤 합니다.

이 문제에서 중점 사항은 면이 인접하지 않게 골라야 하므로, 현재 선택지에서 최댓값은 이전 인덱스의 DP의 최댓값이면서, 행이 다른 DP, 그리고 인덱스가 2개 적은 DP의 다른 행 DP의 최댓값을 비교한 후, 더 큰 것에 현재의 값을 구하는 방식입니다.

for (int i = 2; i <= n; i++) {
    dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + map[0][i];
    dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + map[1][i];
}
result.add(Math.max(dp[0][n], dp[1][n]));

이러한 코드가 가능한 이유는, 다음과 같습니다.

60 70 100 20

70 700 10 900 이 있다고 가정하겠습니다.

20의 입장에서 최대를 선택하는 것은 각 열에 인접하지 않게 선택하여 값을 늘리는 것입니다.

70 70 10 이 될 수 있고, 60 700 이 될 수 있습니다.

(60 700 100 은 20에 100이 인접하므로 될 수 없습니다. || 70 70은 10을  추가로 선택할 수 없으므로 최대값이 되지 못합니다.)

따라서, 점화식은 위의 코드와 같이 구성될 수 있습니다.

2차원 배열이므로, 위 아래 각각 DP를 적용하고, 최종적으로 마지막 인덱스에서 두 DP 중 더 큰 값을 선택하여 값을 도출할 수 있습니다.

이상으로 스티커 자바 풀이를 마치도록 하겠습니다. 감사합니다.!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 원판 돌리기 자바 풀이를 작성하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/17822

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        int t = parseInt(st.nextToken());
        
        Board board = new Board(n, m);
        
        for (int row = 1; row <= n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= m; col++) {
                board.setMap(row, col, parseInt(st.nextToken()));
            }
        }
        
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int x = parseInt(st.nextToken()); // 배수 행
            int dir = parseInt(st.nextToken()); // 방향
            int k = parseInt(st.nextToken()); // 칸 수
            board.rotate(x, dir, k);
        }
        
        System.out.println(board.getSum());
    }
}

class Board {
    int n; // 행의 개수
    int m; // 열의 개수
    int[][] map;
    int[] tmp; // 임시 swap 배열
    
    Board(int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n + 1][m + 1];
        tmp = new int[m + 1];
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }
    
    // dir -> 시계: 0, 반시계: 1
    void rotate(int x, int dir, int k) { // x는 row 배수 형태로
        for (int row = 1; row <= n; row++) {
            if (row % x == 0) { // x의 배수
                swap(map[row], k, dir);
            }
        }

        int leftCol; // 인접한 왼쪽 열
        int rightCol; // 인접한 오른쪽 열
        
        int totalSum = 0; // 총 합
        int totalCnt = 0; // 총 개수
        List<Point> zeros = new ArrayList<>(); // zero가 되는 포인트
        
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= m; col++) {
                int flag = zeros.size(); // zeros.size가 변한다면 인접한 것이 있다는 의미
                int nowValue = map[row][col];

                if (nowValue == 0) continue; // 만약 현재 값이 0인 것은 건너뛰기

                totalSum += nowValue;
                totalCnt++;
                
                if (col == 1) { // 맨 좌측 열은 맨 우측 열 인접하도록 설정하기
                    leftCol = m;
                    rightCol = col + 1; 
                } else if (col == m) {
                    leftCol = m - 1;
                    rightCol = 1;
                } else { // 나머지는 양쪽 열
                    leftCol = col - 1;
                    rightCol = col + 1;
                } 
                
                if (map[row][leftCol] == nowValue) {
                    zeros.add(new Point(row, leftCol));
                }
                
                if (map[row][rightCol] == nowValue) {
                    zeros.add(new Point(row, rightCol));
                }
                
                if (row == 1) { // 맨 윗행은 인접한 행이 바로 아래 행
                    if (nowValue == map[row + 1][col]) zeros.add(new Point(row + 1, col));
                } 
                else if (row == n) { // 맨 아래 행의 인접한 행은 바로 윗행
                    if (nowValue == map[row - 1][col]) zeros.add(new Point(row - 1, col));
                } 
                else {
                    if (nowValue == map[row + 1][col]) zeros.add(new Point(row + 1, col));
                    if (nowValue == map[row - 1][col]) zeros.add(new Point(row - 1, col));
                }

                if (zeros.size() != flag) zeros.add(new Point(row, col)); // 값이 추가되었다는 것을 의미하므로 자신도 추가하기
            }

        }
        
        if (!zeros.isEmpty()) {
            for (Point p : zeros) {
                map[p.row][p.col] = 0; // 인접하여 같은 값도 zero 설정
            }
        } 
        else { // 한 번도 인접한 값이 같은 것이 없음
            if (totalCnt != 0) {
                double avg = (double) totalSum / totalCnt;
                
                for (int row = 1; row <= n; row++) {
                    for (int col = 1; col <= m; col++) {
                        int nowValue = map[row][col];
                        if (nowValue != 0 && avg < nowValue) map[row][col]--; // 평균보다 크다면 --
                        else if (nowValue != 0 && avg > nowValue) map[row][col]++; // 평균보다 작다면 ++
                    }
                }
            }
        }
    }
    
    int getSum() {
        int sum = 0;
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= m; col++) sum += map[row][col];
        }
        return sum;
    }

    // 0, 1, 2, 3, 4, 5
    // k만큼 시계 방향 회전 i + k를 하되, 인덱스를 벗어난 경우 m 빼기
    // i = 2, k = 3 => tmp[5] = 2;
    // i = 3, k = 3 => tmp[6 - 5] = 3;
    void swap(int[] arr, int k, int clockWise) { // k 만큼 스왑
        if(clockWise == 0) {    // 시계 방향 회전
            for (int i = 1; i <= m; i++) {
                int next = i + k > m ? i + k - m : i + k;
                tmp[next] = arr[i];
            }
        }

        // 반시계는 왼쪽으로 칸을 옮기되 0보다 작아질 수 있으므로 m을 더하기
        else {    // 반시계 방향 회전
            for (int i = m; i >= 1; i--) {
                int next = i - k > 0 ? i - k : i - k + m;
                tmp[next] = arr[i];
            }
        }

        System.arraycopy(tmp, 1, arr, 1, arr.length - 1);
    }
    
    static class Point {
        int row;
        int col;
        
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

2. 풀이 중점 사항

회전하기

가장 헷갈린 부분은 회전 처리하는 부분이었습니다.

시계 방향으로 회전을 하기 위해서는 이전 인덱스 i-1의 값이 i로 와야 하기 때문에 --> 이 방향으로 이동이 이뤄져야 합니다.

k 칸을 이동한다고 하는 것은 i번째의 값이 i + k에 도착해야 한다는 것을 의미합니다.

만약 i + k 가 m을 넘어가게 된다면 인덱스 에러가 발생합니다. 이를 해결하기 위해서는 

i + k > m ? i + k - m : i + k라는 수식을 구할 수 있습니다.

예를 들어 다음의 배열이 있습니다. (행과 열이 모두 1, 1부터 이므로 더미의 0번째 인덱스는 무시해야 합니다.)

0, 1, 2, 3, 4, 5

시계방향으로 3만큼 이동

=> 0, 4, 5, 1, 2, 3

3 인덱스는, 3 + 3으로 인해 인덱스가 6이 되어버립니다. 따라서, m만큼 개수를 빼면

6 - 5 = 1이 되어 정상적으로 위치 회전을 할 수 있습니다.

반시계 방향은 <-- 으로 이동해야 합니다.

수식은 i - k > 0? i - k : i - k + m;입니다.

0, 1, 2, 3, 4, 5 

반시계 방향으로 3만큼 이동

=> 0, 3, 4, 5, 1, 2 

1의 경우 3을 뺀다면, -2라서 에러가 발생하므로 5를 더해서 인덱스 3으로 만들 수 있습니다.

3 - 3의 경우 index가 0이지만, 0, 0은 더미로 설정하였으므로

5를 더하여 5로 설정할 수 있습니다. 4, 5는 인덱스가 0보다 크므로 i - k로 해결할 수 있습니다.

void swap(int[] arr, int k, int clockWise) { // k 만큼 스왑
    if(clockWise == 0) {    // 시계 방향 회전
        for (int i = 1; i <= m; i++) {
            int next = i + k > m ? i + k - m : i + k;
            tmp[next] = arr[i];
        }
    }

    // 반시계는 왼쪽으로 칸을 옮기되 0보다 작아질 수 있으므로 m을 더하기
    else {    // 반시계 방향 회전
        for (int i = m; i >= 1; i--) {
            int next = i - k > 0 ? i - k : i - k + m;
            tmp[next] = arr[i];
        }
    }

    System.arraycopy(tmp, 1, arr, 1, arr.length - 1);
}

점을 기준으로 특정 좌표를 회전시키거나 이렇게 swap 하는 유형은 실수하기 좋은 유형이므로 천천히 자세하게 적어가면서 해결해야 함을 느낄 수 있었습니다.

이성으로 원판 돌리기 자바 풀이를 마치겠습니다. 감사합니다.!!!