๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 1495_๊ธฐํƒ€๋ฆฌ์ŠคํŠธ

๋ฟŒ์•ผ._. 2023. 11. 29. 23:43

Silver I

๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/1495)

< ๊ธฐํƒ€๋ฆฌ์ŠคํŠธ >

 

๋ฌธ์ œ ํ’€์ด 

 

์ฒ˜์Œ์—๋Š” queue๋ฅผ ์‚ฌ์šฉํ•ด์„œ ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ๋ณผ๋ฅจ์„ add์™€ pop์„ ํ†ตํ•ด ๊ตฌํ–ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ๊ตฌํ˜„ํ•  ๊ฒฝ์šฐ ๋ฉ”๋ชจ๋ฆฌ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•ด์„œ ์–ด๋–ป๊ฒŒ ๊ณ ์ณ์•ผ ํ• ์ง€ ๋ชฐ๋ž๋‹ค. 

 

์ฐพ์•„๋ณธ ๊ฒฐ๊ณผ 0 ์ด์ƒ M์ดํ•˜์˜ ๊ฐ’๋งŒ ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ ๋ฐฐ์—ด์„ m+1๋งŒํผ ์„ ์–ธํ•œ ํ›„์— ๋ฐฐ์—ด[๋ณผ๋ฅจ] = ์ธ๋ฑ์Šค๋กœ ๊ฐ’์„ ๊ตฌํ•˜์—ฌ ๋ฉ”๋ชจ๋ฆฌ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š”๋‹ค.

 

์˜ˆ๋ฅผ ๋“ค์–ด

1 5 10

์ด๋ผ๋ฉด temp [5]=1๋กœ ์ดˆ๊ธฐํ™”ํ•œ ํ›„์— 0๋ฒˆ์งธ ๊ณก์„ ์—ฐ์ฃผํ•˜๊ธฐ ์œ„ํ•ด ๋ณผ๋ฅจ์„ ๋ฐ”๊พผ๋‹ค๊ณ  ํ•˜์ž.

temp [10]=2, temp [0]=2๊ฐ€ ๋œ๋‹ค. 0 ์ด์ƒ M์ดํ•˜์ธ ๋ฐฐ์—ด์„ ์ „์ฒด ํƒ์ƒ‰ํ•˜์—ฌ ๋ฐฐ์—ด ๊ฐ’์ด 2์ธ ์ธ๋ฑ์Šค ์ค‘์— ์ตœ๋Œ“๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

 my solution (Java)

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

public class _1495_ { // ๊ธฐํƒ€๋ฆฌ์ŠคํŠธ

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

		int n = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(bf.readLine());
		int arr[] = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int temp[] = new int[m + 1];
		temp[s] = 1;
		boolean flag = false;

		for (int i = 0; i < n; i++) {
			flag = false;
			ArrayList<Integer> list = new ArrayList<>();
			for (int j = 0; j < m + 1; j++) {
				if (temp[j] == i + 1) {
					if (j + arr[i] <= m) {
						list.add(j + arr[i]);
						flag = true;
					}
					if (j - arr[i] >= 0) {
						list.add(j - arr[i]);
						flag = true;
					}
				}
			}
			for (int j : list) {
				temp[j] = i + 2;
			}
			if (!flag) {
				break;
			}
		}

		int result = -1;
		for (int i = 0; i < m + 1; i++) {
			if (temp[i] == n + 1) {
				result = Math.max(result, i);
			}
		}
		System.out.println(result);
	}
}
๋ณ€์ˆ˜)
n, s, m : ๊ณก์˜ ๊ฐœ์ˆ˜, ์‹œ์ž‘ ๋ณผ๋ฅจ, ๋ณผ๋ฅจ ์ตœ๋Œ“๊ฐ’
arr : ๊ฐ ๊ณก์ด ์‹œ์ž‘ํ•˜๊ธฐ ์ „์— ์ค„ ์ˆ˜ ์žˆ๋Š” ๋ณผ๋ฅจ์˜ ์ฐจ์ด
temp : ๋ณผ๋ฅจ ์กฐ์ ˆ ๋ฐฐ์—ด
flag : ๋งˆ์ง€๋ง‰ ๊ณก์„ ์—ฐ์ฃผํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ํŒ๋‹จํ•˜๋Š” boolean 
list : ์ค‘๊ฐ„์— ๋ฐฐ์—ด ๊ฐ’์„ ๋ณ€๊ฒฝํ•˜์ง€ ์•Š๊ฒŒ ํ•˜๊ธฐ ์œ„ํ•ด ์ €์žฅํ•˜๋Š” ArrayList
result : ๋งˆ์ง€๋ง‰ ๊ณก์˜ ๋ณผ๋ฅจ ์ค‘ ์ตœ๋Œ“๊ฐ’

 

temp [s]=1๋กœ ์ €์žฅํ•œ๋‹ค. ๋ณผ๋ฅจ s๊ฐ€ ์‹œ์ž‘ ๋ณผ๋ฅจ์ด๋ฏ€๋กœ 1์„ ์ €์žฅํ•œ๋‹ค.

arr ๋ฐฐ์—ด์„ ์ „์ฒด ์ˆœํ™˜ํ•˜๋ฉฐ temp ๋ฐฐ์—ด๋„ ๊ฐ™์ด ์ˆœํ™˜ํ•œ๋‹ค. temp ๋ฐฐ์—ด์˜ ๊ฐ’์ด i+1 ๊ฐ’์ด๋ผ๋ฉด ๋‹ค์Œ ๊ณก์„ ์—ฐ์ฃผํ•˜๊ธฐ ์œ„ํ•ด ๋ณผ๋ฅจ ์กฐ์ ˆ์„ ํ•ด์•ผ ํ•˜๋ฏ€๋กœ P+arr [i], P-arr [i]์„ ๊ตฌํ•œ ํ›„ 0 ์ด์ƒ M์ดํ•˜ ๊ฐ’์ด๋ผ๋ฉด i+2 ๊ฐ’์œผ๋กœ ์ €์žฅํ•œ๋‹ค.

 

์ตœ์ข… temp ๋ฐฐ์—ด์„ ์ˆœํ™˜ํ•˜๋ฉฐ ๊ฐ’์ด n+1์ธ ๊ฐ’ ์ค‘์— ์ตœ๋Œ“๊ฐ’์„ ๊ตฌํ•ด ์ถœ๋ ฅํ•œ๋‹ค.