<stdio.han>

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

[정답 코드]

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

public class Main {
    static int[][] houses;
    static int[][] cost;
    static int N;

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

        N = Integer.parseInt(st.nextToken());
        houses = new int[N][3];
        cost = new int[N][3];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 3; j++) {
                houses[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 초기값 세팅
        cost[0][0] = houses[0][0];
        cost[0][1] = houses[0][1];
        cost[0][2] = houses[0][2];

        System.out.println(Math.min(Math.min(dp(N-1,0), dp(N-1,1)), dp(N-1,2)));
    }

    // 로직
    public static int dp(int N, int color) {
        if (cost[N][color] == 0) {
            if (color == 0) {
                return cost[N][color] = Math.min(dp(N-1, 1), dp(N-1, 2)) + houses[N][color];
            }
            if (color == 1) {
                return cost[N][color] = Math.min(dp(N-1, 0), dp(N-1, 2)) + houses[N][color];
            }
            if (color == 2) {
                return cost[N][color] = Math.min(dp(N-1, 0), dp(N-1, 1)) + houses[N][color];
            }
        }
        return cost[N][color];
    }
}

[설명]

저번 DP문제에서 설명했듯이 DP 문제는 3가지 방법을 따라야 한다.

1. 테이블 정의

2. 점화식 찾기

3. 초기값 정하기

1. 테이블 정의하기

dp[N] = N일째 집일 때 집을 칠하는 최소 비용

2. 점화식 찾기

cost [N][Red] = Math.min(dp[N-1][Green], dp[N-1][Blue]) + houses[N][Red]

cost [N][Green] = Math.min(dp[N-1][Red], dp[N-1][Blue]) + houses[N][Green]

cost [N][Blue] = Math.min(dp[N-1][Red], dp[N-1][Green]) + houses[N][Blue]

Math.min(Math.min(dp[N-1][Red], dp[N-1][Green]), dp[N-1][Blue])

3. 초기값 세팅

cost[0][0] = houses[0][0];
cost[0][1] = houses[0][1];
cost[0][2] = houses[0][2];

나머지는 코드와 같다.

나는 스스로 테이블정의, 점화식찾기, 초기값 세팅을 처음으로 스스로 구해냈다! 하지만 여기까지였다. 그 다음 코드로 구현하는 부분에서 막혀버려서 구글링을해 코드를 구현했다.

https://school.programmers.co.kr/learn/courses/30/lessons/64061

[시행 착오]

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        String basket = "0";
        for(int i=0;i<moves.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[j][moves[i] - 1] != 0){
                    int tmp = board[j][moves[i] - 1];
                    board[j][moves[i] - 1] = 0;
                    if(basket.substring(basket.length()-1).equals(Integer.toString(tmp))){
                        answer+=2;
                        basket = basket.substring(0,basket.length()-1);
                        break;
                    } else {
                        basket += (String.valueOf(tmp));
                    }
                    break;
                }
            }
        }
        return answer;
    }
}

[정답 코드]

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        
        for(int i=0;i<moves.length;i++){
            for(int j=0;j<board.length;j++){
                if(board[j][moves[i]-1] != 0){
                    if(!stack.empty() && stack.peek() == board[j][moves[i]-1]){
                        answer+=2;
                        stack.pop();
                            board[j][moves[i]-1]=0;
                        break;
                    } else {
                        stack.push(board[j][moves[i]-1]);
                        board[j][moves[i]-1]=0;
                        break;
                    }
                } 
            }
        }     
        return answer;
    }
}

[설명]

이 문제는 시물레이션 문제로 보기에는 어려워 보이지만 생각보다 쉬운 문제라고 생각한다.

아이디어는 크레인이 인형을 뽑을 때마다 해당 위치에 가장 위에 쌓여있는 인형을 뽑은 후 해당 위치를 0 으로 변경해준다.

뽑은 인형은 stack에 담고, stack.peek() 함수를 사용해 stack의 가장 최근 숫자를 확인 후 뽑은 인형과 같다면 stack.pop()을 해 스택에서 제거해준다.

이론은 간단한데 처음에 틀렸던 이유는 스택을 사용하면 쉬운데 스택이 순간 생각나지 않아서 문자열로 풀다가 문제 일부분만 맞았었다. 문자열의 마지막숫자와 뽑은 인형을 비교해 나가는 로직이였는데 안되는 이유는 문제에서 인형의 번호가 0~100 까지 존재해 문자열의 마지막숫자로 비교하면 틀리게 되는것이였다. 

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

[시행 착오]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        if (N <= 3) {
            System.out.println(1);
        } else if (N % 3 == 0) {
            System.out.println(N / 3);
        } else if (N % 3 == 1 && N % 2 == 0) {
            System.out.println((N / 3));
        } else if (N % 3 == 1){
            System.out.println((N / 3) + 1);
        } else if (N % 2 == 0) {
            System.out.println(N / 2);
        } else {
            System.out.println((N / 3) + 1);
        }
    }
}

[정답 코드]

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

public class Main {

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

        int N = Integer.parseInt(st.nextToken());
        int[] dp = new int[N + 1];
        dp[0] = dp[1] = 0;

        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1; // 1을 뺀값
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1); // 1을 뺀값과 2로 나눈값준 최솟값
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1); // (1을 뺀 값과 2로 나눈 값중 최솟값) 과 3으로 나눈값중 최솟값
            }
        }
        System.out.println(dp[N]);
    }
}

[설명]

이 문제는 DP 문제이다.

DP 문제는 3가지 단계를 생가해야 된다고 한다.

1. 테이블 정의

2. 점화식 찾기

3. 초기값 정하기

1. 테이블 정의

dp[i] = i를 1로 만들때 연산을 해야하는 횟수의 최솟값

2. 점화식 찾기

dp[12] 을 예로들자면

3으로 나누거나 (dp[12] = dp[4] + 1) = (dp[i] = dp[i/3] + 1)

2로 나누거나 (dp[12] = dp[6] + 1) = (dp[i] = dp[i/2] + 1)

1을 빼거나 (dp[12] = dp[11] + 1) = dp[i] = dp[i-1] + 1)

-> dp[12] = min(dp[4] + 1, dp[6] + 1, dp[11] + 1)

-> dp[i] = min(dp[i/3] + 1, dp[i/2] + 1, dp[i-1] + 1)

3. 초기값 정하기

dp[0] = dp[1] = 0

사실 이 모든 아이디어는 내 아이디어가 아니다. dp 문제는 가장 자신없어 하는 분야이기도하고 점화식을 계산하는법을 도저히 떠올릴수가 없다ㅠㅠ. 그래서 어느 한 블로그를 참고했다. 내가 푼 문제라고 볼 수 없다.

참고 : 

https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-1463%EB%B2%88-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0-Java-%EC%9E%90%EB%B0%94

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

[정답 코드1]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int count = 0;
        while (N > 0) {
            if (N % 5 == 0) { // N이 5로 나눠질수 있을 경우 5로 나눠버린 후 출력
                count += N / 5; // 5로 나눈 몫을 count 에 더함
                System.out.println(count);
                return;
            }
            if (N < 3) {
                System.out.println("-1"); // N이 3보다 적을 경우에는 -1
                return;
            }
            N-=3; // N이 5로 안나눠질 경우에는 3kg 짜리 하나를 만듬
            count++;
        }
        System.out.println(count);
    }
}

[설명]

처음에 작성했던 코드이다. 정말 단순하게 N이 5로 나눠질 때 까지 3씩 빼면서 count 를 늘렸다. 풀고나서 다른사람들이 작성했던 코드를 봤을때 깜짝놀랐었다. 이렇게 단순하게 푸는게 아닌 수학적인 방법을 사용하면 코드도 더 간결하고 쉽게 풀 수 있엇다.

[정답 코드 2]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());

        if (N == 4 || N == 7) { // N이 4이거나 7일 경우에는 3이나 5로 나눌수 없다.
            System.out.println(-1);
        } else if (N % 5 == 0) { // N이 5로 바로 나눠질 경우
            System.out.println(N / 5);
        } else if (N % 5 == 1 || N % 5 == 3) { // N이 6, 8, 11, 13, 16 등일 경우
            System.out.println((N / 5) + 1);
        } else if (N % 5 == 2 || N % 5 == 4) { // N이 9, 12, 14, 17, 19 등일 경우
            System.out.println((N / 5) + 2);
        }
    }
}

[설명]

다른 사람이 작성한 글을 보며 대단하다고 생각했다. 조건문이 4개가 있는데 먼저

N이 4 또는 7일 경우에는 3kg 포대와 5kg 포대를 아무리 사용해도 나눠지지 않기 때문에 "-1" 을 출력해준다.

혹은 N이 5로 나눠질 경우에는 N/5 를 출력해준다.

혹은 N이 6, 8, 11, 13, 16 등 N%5 의 값이 1 또는 3일 경우 (N / 5) + 1 을 출력해준다.

혹은 N이 9, 12, 14, 17, 19 등 N%5의 값이 2 또는 4 일 경우 (N / 5) + 2 를 출력해준다.

자세한 설명은 참고한 블로그를 링크로 달아놓겠다.

참고한 블로그 : 

https://st-lab.tistory.com/72

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

[정답 코드]

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

public class Main {
    static int N, M;
    static int[][] room;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1}; // 북, 동, 남, 서 순서
    static int count = 0;
    static boolean flag;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");

        int robotX = Integer.parseInt(st.nextToken());
        int robotY = Integer.parseInt(st.nextToken());
        int robotHead = Integer.parseInt(st.nextToken());
        room = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                room[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        clean(robotX, robotY, robotHead);
        System.out.println(count);
    }

    static void clean(int x, int y, int head) {
        // 현재 위치가 더럽다면 청소
        if (room[x][y] == 0) {
            room[x][y] = 2; // 현재 위치 청소
            count++;
        }
        flag = false;
        for (int i = 0; i < 4; i++) {
            int nextHead = (head + 3) % 4; // 반시계 방향으로 90도 회전한 방향이 청소할 구역인지
            int nextX = x + dx[nextHead];
            int nextY = y + dy[nextHead];
            if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
                if (room[nextX][nextY] == 0) {
                    clean(nextX, nextY, nextHead);
                    flag = true; // 청소할 구역이 있는 경우
                    break;
                }
            }
            head = (head + 3) % 4; // 반시계 90도 회전
        }


        if (!flag) { // 네 방향이 모두 청소된곳이거나 벽인 경우
            int nextHead = (head + 2) % 4; // 후진
            int nextX = x + dx[nextHead];
            int nextY = y + dy[nextHead];
            if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) { // 후진할 공간이 있을 경우
                if (room[nextX][nextY] != 1) {
                    clean(nextX, nextY, head); // 후진
                }
            }
        }
    }
}

[설명]

이 문제는 4방탐색을 활용한 구현문제이다.

문제 설명이 이상해 이해하기 어렵지만 간단하게 정리하자면

1. 현재 위치를 청소한다.

2. 바라보는 방향에서 반시계 90도로 회전하면 청소할 수 있는지 탐색한다.

3 - 1. 청소할 수 있다면 전진한다. 그 후 1번으로 간다.

3 - 2. 청소할 수 없다면 후진한다.

4 - 1. 후진할 수 있다면 1번으로 간다.

4 - 2. 후진할 수 없다면 종료한다.

먼저 방의 로봇청소기의 위치와 방향을 clean 함수에 넣고 실행시킨다.

clean 함수는 로봇청소기의 위치가 청소해야할곳이라면 청소를 해 해당 위치를 임의의 숫자 2로 변경해준다.

그 후 4방탐색을 실시하는데 중요한 점은 4방탐색을 할 때 내가 바라보는 방향에서 반시계로 90도 씩 돌아가는 순서대로 탐색을 해야하는 것이다.

(head + 3) % 4 를 했을 경우 내가 바라보는 방향 head에서 반시계로 90도 돌게된다. 그리고 이를 4번할 경우 다시 원래방향을 바라보게 된다.

예를들어 head 가 0(북쪽) 일경우

(0 + 3) % 4 = 3(서쪽)

(3 + 3) % 4 = 2(남쪽)

(2 + 3) % 4 = 1(동쪽)

(1 + 3) % 4 = 0(북쪽)

이렇게 네 방향을 탐색했는데 모두 청소된 곳이거나 벽일경우 

(head + 2) % 4 를 하게되면 180도 뒤를 바라보게 된다.

만약 head 가 0(북쪽) 일경우

(0 + 2) % 4 = 2(남쪽)

이므로 후진을 할 수 있다.