[Baekjoon] 1495_๊ธฐํ๋ฆฌ์คํธ
๋ฌธ์ (์ถ์ฒ: https://www.acmicpc.net/problem/1495)
< ๊ธฐํ๋ฆฌ์คํธ >
๋ฌธ์ ํ์ด
์ฒ์์๋ queue๋ฅผ ์ฌ์ฉํด์ ๊ฐ๋ฅํ ๋ชจ๋ ๋ณผ๋ฅจ์ add์ pop์ ํตํด ๊ตฌํ๋ค. ์ด๋ ๊ฒ ๊ตฌํํ ๊ฒฝ์ฐ ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋ฐ์ํด์ ์ด๋ป๊ฒ ๊ณ ์ณ์ผ ํ ์ง ๋ชฐ๋๋ค.
์ฐพ์๋ณธ ๊ฒฐ๊ณผ 0 ์ด์ M์ดํ์ ๊ฐ๋ง ๊ฐ๋ฅํ๋ฏ๋ก ๋ฐฐ์ด์ m+1๋งํผ ์ ์ธํ ํ์ ๋ฐฐ์ด[๋ณผ๋ฅจ] = ์ธ๋ฑ์ค๋ก ๊ฐ์ ๊ตฌํ์ฌ ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋ฐ์ํ์ง ์๋๋ค.
์๋ฅผ ๋ค์ด
1 5 10
5
์ด๋ผ๋ฉด 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์ธ ๊ฐ ์ค์ ์ต๋๊ฐ์ ๊ตฌํด ์ถ๋ ฅํ๋ค.