๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/17626
- ๋ผ๊ทธ๋์ฃผ๋ 1770๋ ์ ๋ชจ๋ ์์ฐ์๋ ๋ท ํน์ ๊ทธ ์ดํ์ ์ ๊ณฑ์์ ํฉ์ผ๋ก ํํํ ์ ์๋ค๊ณ ์ฆ๋ช ํ์๋ค.
- ์ด๋ค ์์ฐ์๋ ๋ณต์์ ๋ฐฉ๋ฒ์ผ๋ก ํํ๋๋ค.
- ์๋ฅผ ๋ค๋ฉด, 26์ 52๊ณผ 12์ ํฉ์ด๋ค; ๋ํ 42 + 32 + 12์ผ๋ก ํํํ ์๋ ์๋ค.
- ์ญ์ฌ์ ์ผ๋ก ์์ฐ์ ๋ช ์๋ค์๊ฒ ๊ณตํต์ ์ผ๋ก ์ฃผ์ด์ง๋ ๋ฌธ์ ๊ฐ ๋ฐ๋ก ์์ฐ์๋ฅผ ๋ท ํน์ ๊ทธ ์ดํ์ ์ ๊ณฑ์ ํฉ์ผ๋ก ๋ํ๋ด๋ผ๋ ๊ฒ์ด์๋ค.
- 1900๋ ๋ ์ด๋ฐ์ ํ ์์ฐ๊ฐ๊ฐ 15663 = 1252 + 62 + 12 + 12๋ผ๋ ํด๋ฅผ ๊ตฌํ๋๋ฐ 8์ด๊ฐ ๊ฑธ๋ ธ๋ค๋ ๋ณด๊ณ ๊ฐ ์๋ค.
- ์ข ๋ ์ด๋ ค์ด ๋ฌธ์ ์ ๋ํด์๋ 56์ด๊ฐ ๊ฑธ๋ ธ๋ค: 11339 = 1052 + 152 + 82 + 52.
- ์์ฐ์ n์ด ์ฃผ์ด์ง ๋, n์ ์ต์ ๊ฐ์์ ์ ๊ณฑ์ ํฉ์ผ๋ก ํํํ๋ ์ปดํจํฐ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ ๋ ฅ์ ํ์ค์ ๋ ฅ์ ์ฌ์ฉํ๋ค. ์ ๋ ฅ์ ์์ฐ์ n์ ํฌํจํ๋ ํ ์ค๋ก ๊ตฌ์ฑ๋๋ค. ์ฌ๊ธฐ์, 1 ≤ n ≤ 50,000์ด๋ค.
- ์ถ๋ ฅ์ ํ์ค์ถ๋ ฅ์ ์ฌ์ฉํ๋ค. ํฉ์ด n๊ณผ ๊ฐ๊ฒ ๋๋ ์ ๊ณฑ์๋ค์ ์ต์ ๊ฐ์๋ฅผ ํ ์ค์ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- n + 1 ํฌํค์ ๋ฐฐ์ด์ ์ ๊ณฑ์์ ๊ฐ์๋ฅผ ์ ์ฅํ๊ธฐ ์ํด ์์ฑํ๋ค.
- ๊ทธ๋ฆฌ๊ณ ๋ฐฐ์ด์ 1๋ถํฐ n๊น์ง ์ด๊ธฐ๊ฐ์ ๋ณธ์ธ์ ์๋ก ์ ์ฅํ๋ค.
- ์๋ํ๋ฉด ์ ์ผ ํฐ ๊ฒฝ์ฐ์ ์๊ฐ 1์ ์ ๊ณฑ์ผ๋ก ํฉ์ ๋ํ๋ด๋ ๊ฒ์ด๊ธฐ ๋๋ฌธ์ด๋ค.
- ๊ทธ๋ฆฌ๊ณ ์ด์ค for๋ฌธ์ ์ฌ์ฉํ์ฌ i๋ฒ์งธ ๋ฐฐ์ด์ i๋ฒ์งธ ๋ฐฐ์ด์ ๊ฐ๊ณผ i - j * j ๋ฒ์งธ ๋ฐฐ์ด ๊ฐ์ 1์ ๋ํ ๊ฐ๊ณผ ๋น๊ตํด์ ๋ ์์ ๊ฐ์ ์ ์ฅํ๋ค.
- ์ ๊ณฑ์๊ฐ ๊ธฐ์กด ์ซ์๋ณด๋ค ํฌ๋ฉด ์๋๋ฏ๋ก j์ ๋ฒ์๋ j * j ๊ฐ i๋ณด๋ค ์์ ๋๊น์ง๋ก ์ ํํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- ์ฒ์์๋ i๋ฒ์งธ ๋ฐฐ์ด์ ์ซ์๊ฐ ๊ท์น์ฑ์ด ์์๊น ์ถ์ด์ ์ด์ฌํ ์ฐพ์๋ดค์ง๋ง ์คํจํ์๊ณ ... ๋ฌธ์ ๋ฅผ ๋ณด์๋ง์ ๋ ์ฌ๋ ธ๋ '๋ฐฐ์ด์ ์ด์ ๊ฐ์ + 1์ ํ์ฌ ํ๋ฉด๋์ง ์์๊น'๋ ์๊ฐ์ ํ์ฉํด์ ํ์๋ค
- ๊ทผ๋์ ํ์๋ dp๋ฌธ์ ์ค์์ ์ ์ผ ์ด๋ ต๊ฒ ํ์๋ ๊ฒ ๊ฐ๋ค ใ ใ
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ17626 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// ์
๋ ฅ๊ฐ
int n = Integer.parseInt(br.readLine());
// ์ ๊ณฑ๊ฐ์ ๊ฐ์๋ฅผ ์ ์ฅํ ๋ฐฐ์ด
int arr[] = new int[n + 1];
// ๋ฐฐ์ด์ i๋ฒ์งธ ๊ฐ์ i๊ฐ์ผ๋ก ์ ์ฅ
// ์ต๋ ํ์ํ ๊ฐ์๋ 1์ ์ ๊ณฑ์ผ๋ก ๋ค ์ฑ์ฐ๋ ๊ฒฝ์ฐ์ด๋ฏ๋ก
for(int i = 1; i <= n; i++){
arr[i] = i;
}
for(int i = 1; i <= n; i++){
// ์ ๊ณฑ์๊ฐ ๊ธฐ์กด๊ฐ๋ณด๋ค ํฌ๋ฉด ์๋๋ฏ๋ก
// j * j ๊ฐ i๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์๋๊น์ง ๋ฐ๋ณต
for(int j = 1; j * j <= i; j++){
// i๋ฒ์งธ ๋ฐฐ์ด์ ๊ฐ์ i๋ฒ์งธ ๋ฐฐ์ด์ ๊ฐ๊ณผ
// i๋ฒ์งธ ๋ฐฐ์ด์์ j์ ์ ๊ณฑ๊ฐ์ ๋บ ๊ฐ์์ 1 ๋ํ๊ฐ ์ค
// ๋ ์์ ๊ฐ์ ์ ์ฅ
arr[i] = Math.min(arr[i], arr[i - j * j] + 1);
}
}
System.out.println(arr[n]);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 1260 DFS์ BFS (0) | 2024.08.01 |
---|---|
[Java] BOJ 1012 ์ ๊ธฐ๋ ๋ฐฐ์ถ (0) | 2024.07.31 |
[Java] BOJ 11727 2รn ํ์ผ๋ง 2 (0) | 2024.07.30 |
[Java] BOJ 11726 2รn ํ์ผ๋ง (0) | 2024.07.29 |
[Java] BOJ 11659 ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ 4 (0) | 2024.07.29 |