프로그래머스 - 숫자 변환하기, 택배 배달과 수거하기, 백준 16918

🔢 프로그래머스 : 숫자 변환하기

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

프로그래머스

 

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

 

🔢 이 문제 예전에 백준에서 본 문제와 유사하다고 생각했는데, 백준 1463 - 1로 만들기 이 문제와 유사하다. 

🔢 동적 계획법, BFS 다 가능한 문제 

 

🔢 동적 계획법 코드

class Solution {
    public int solution(int x, int y, int n) {
        int[] DP = new int[y+1];
        for (int i = x + 1; i <= y; i++) {
            int temp = 1000010;
            if (i >= n && i - n >= x) {
                temp = Math.min(temp, DP[i - n] + 1);
            } 
            if (i / 2 >= x && i % 2 == 0) {
                temp = Math.min(temp, DP[i / 2] + 1);
            }
            if (i / 3 >= x && i % 3 == 0) {
                temp = Math.min(temp, DP[i / 3] + 1);
            }
            
            DP[i] = temp;
        }
        
        return DP[y] >= 1000010 ? -1 : DP[y];
    }
}

 

🔢 BFS 코드

import java.util.*;
class Solution {
    public int solution(int x, int y, int n) {
        boolean[] visited = new boolean[y+1];
        Queue<Num> queue = new LinkedList<>();
        queue.add(new Num(x, 0));
        visited[x] = true;
        
        while (!queue.isEmpty()) {
            Num poll = queue.poll();
            if (poll.value == y) {
                return poll.count;
            }
            
            if (poll.value * 2 <= y && !visited[poll.value * 2]) {
                queue.add(new Num(poll.value * 2, poll.count+1));
                visited[poll.value * 2] = true;
            }
            
            if (poll.value * 3 <= y && !visited[poll.value * 3]) {
                queue.add(new Num(poll.value * 3, poll.count + 1));
                visited[poll.value * 3] = true;
            }
            
            if (poll.value + n <= y && !visited[poll.value + n]) {
                queue.add(new Num(poll.value + n, poll.count + 1));
                visited[poll.value + n] = true;
            }
        }
        
        return -1;
    }
    
    class Num {
        int value;
        int count;
        
        Num (int value, int count) {
            this.value = value;
            this.count = count;
        }
    }
    
}

 

🔢 이건 코드와 별개로 궁금해서 두 테스트 결과를 모두 캡처 떠왔는데, 왼쪽이 DP 오른쪽이 BFS이다. 

🔢 프로그래머스에서 테스트 케이스를 공개하지는 않는데, 몇 번 돌려보니 5, 6, 9, 10, 11 이 쪽이 데이터가 많은 테스트인 것 같았다(처음에 여기서 시간초과 났음)

🔢 비교적 DP가 BFS보다 시간소모가 일정하게 나오는 것 같긴 하다. 

 

 

 

---

📦 프로그래머스 : 택배 배달과 수거하기

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

프로그래머스

 

 

 

📦 뒤에 있는 것들을 빠르게 해치우는 것이 최대한 적게 움직일 수 있다. 

 

 

📦 배달을 해 준 만큼 수거도 가능하다. 따라서 cap만큼 (한 번에 실어나를 수 있는 양) 마지막 칸에 다 내려주고, 내려준 크기만큼 수거해간다. 

📦 코드 로직

• if 문 : 배달 / 수거 해가야 할 양이 남아있다면
• while 문 : cap만큼 배달 / 수거를 하면서 count를 증가시킨다. 
• 다 도달하면 deliver / pick은 각 지점에서의 배달 / 수거 양이므로 다시 빼준다. 
• answer += count * (i + 1) * 2 
  • count는 해당 지점에 들려야하는 횟수이다. 왕복이므로 * 2, index는 1부터 시작하므로 i + 1

 

📦 전체코드 

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int deliver = 0;
        int pick = 0;
    
        for (int i = n-1; i >= 0; i--) {
            int count = 0;
            if (deliveries[i] > 0 || pickups[i] > 0) {
                while (deliver < deliveries[i] || pick < pickups[i]) {
                    count++;
                    deliver += cap;
                    pick += cap;
                }
                deliver -= deliveries[i];
                pick -= pickups[i];
                
                answer += count * (i+1) * 2;
            }
        }
        return answer;
    }
}

 

 

 

 

 

 

---

 

💣 백준 16918 : 봄버맨

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

16918번: 봄버맨

 

💣 실버1 문제인데 생각보다 구현할 때 헷갈렸던 문제... (내가 물골드...인걸수도) 

💣 문제의 상황을 해석해보면 아래와 같다. 

• 0초 : 초기상태
• 1초 : 봄버맨 안 움직임
• 2초 : 빈칸에 폭탄 설치
• 3초 : 폭탄이 터짐(초기에 설치한)
• 4초 : 빈칸에 폭탄 설치
• 5초 : 폭탄이 터짐(2초에 설치한) 
• 6초 : 빈칸에 폭탄 설치 

💣 코드 흐름 

• 0, 1초를 제외하면 계속 짝수 초에는 폭탄 설치, 홀수 초에는 폭탄 폭발 이렇게 번갈아가면서 일어나는 것을 볼 수 있다. 
• 따라서 아래 코드처럼 먼저 curTime(현재 시간)을 +1 해주고, while문을 시작한다.
• 짝수일 때는 폭탄 설치(setBomb())
• 홀수 일때는 bombLife로 터질 위치 계산하고, burst로 터뜨린다. temp는 터지는 애들 표기용 임시 배열

curTime++;
while (curTime <= time) {
	if (curTime % 2 == 0) {
		setBomb();
	} else {
		bombLife();
		burst();
		temp = new int[row][col];
	}
	curTime++;
}

 

 

💣 전체코드

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

public class Main {
    private static char[][] map;
    private static int[][] timeMap, temp;
    private static int[] dirX = { -1, 0, 1, 0};
    private static int[] dirY = {0, 1, 0, -1};
    private static int row, col, time, curTime = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        time = Integer.parseInt(st.nextToken());

        map = new char[row][col];
        temp = new int[row][col];
        timeMap = new int[row][col];
        for (int i = 0; i < row; i++) {
            String str = br.readLine();
            for (int j = 0; j < col; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == 'O') {
                    timeMap[i][j] = 3;
                }
            }
        }
        curTime++;
        
        // 2초부터 시작
        while (curTime <= time) {

            if (curTime % 2 == 0) {
                setBomb();
            } else {
                bombLife();
                burst();
                temp = new int[row][col];
            }
            curTime++;
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    // 폭탄 설치
    private static void setBomb() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (map[i][j] == '.') {
                    map[i][j] = 'O';
                    timeMap[i][j] = curTime + 3;
                }
            }
        }
    }

    // 터진 애들 빈칸으로 한번에 만들어주기
    private static void burst() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (temp[i][j] == -1) {
                    map[i][j] = '.';
                    timeMap[i][j] = 0;
                }
            }
        }
    }

    private static void bombLife() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (timeMap[i][j] == curTime) {
                    temp[i][j] = -1;
                    findBurstSpot(i, j);
                }
            }
        }

    }

    private static void findBurstSpot(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextX = x + dirX[i];
            int nextY = y + dirY[i];

            if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
                continue;
            }
            if (temp[nextX][nextY] == -1) {
                continue;
            }
            if (timeMap[nextX][nextY] == curTime) {
                continue;
            }
            map[nextX][nextY] = '.';
            timeMap[nextX][nextY] = 0;
        }
    }

}