[伯俊]16922号ローマ数字-Java,Java
難易度
銀色.
に答える
<実装エラー>
static void back(int count, int sum) {
if (count == n) {
set.add(sum);
return;
}
back(count + 1, sum + 1);
back(count + 1, sum + 5);
back(count + 1, sum + 10);
back(count + 1, sum + 50);
}
最初にbacktrackingを以下のように実装し,HashSetを用いて繰返し値を除去した.しかし、結果はタイムアウトです.
理由を知ると,HashSetにとって,以前に蓄積した値と入力したsum値を最初から比較することで,値を増やす内部アルゴリズムがタイムアウトすることが分かった.
さらに大きな理由は,上記のコードを実行する際の時間的複雑度がO(4^20=199951162776)であり,1億をはるかに超えるためである.
<ソリューション>
バックトラッキングで枝を使うべきで、15650番NとM(2)番を参考にしたほうがいいです.
ここで、VX、VXV、XVVで作成された数字は20で、同じです.
この場合、重複数列であり、重複数列を防止するために、文では初期値がゼロでないことから始まる.
public static void back(int start, int sum, int count) {
if (count == n) {
if (!visit[sum]) {
visit[sum] = true;
cnt++;
}
return;
}
for (int i = start; i < 4; i++) {
back(i, sum + num[i], count + 1);
}
}
方法2-ブルートフォース1の個数がiの場合、5の個数はj=n-i、10の個数はk=n-i-j、50の個数はl=n-i-j-k
private static void bruteforce() {
for (int i = 0; i <= n; i++) { // 1의 개수
for (int j = 0; j <= n - i; j++) { //5의 개수
for (int k = 0; k <= n - i - j; k++) { // 10의 개수
int l = n - i - j - k; // 50의 개수
int sum = i * 1 + j * 5 + k * 10 + l * 50;
if (!visit[sum]) {
cnt++;
visit[sum] = true;
}
}
}
}
}
コード#コード#
package 백트래킹;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ16922 {
static int n;
static boolean[] visit;
static int cnt;
static int[] num = {1, 5, 10, 50};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
visit = new boolean[50 * 20 + 1];
bruteforce();
// back(0, 0, 0);
System.out.println(cnt);
}
private static void bruteforce() {
for (int i = 0; i <= n; i++) { // 1의 개수
for (int j = 0; j <= n - i; j++) { //5의 개수
for (int k = 0; k <= n - i - j; k++) { // 10의 개수
int l = n - i - j - k; // 50의 개수
int sum = i * 1 + j * 5 + k * 10 + l * 50;
if (!visit[sum]) {
cnt++;
visit[sum] = true;
}
}
}
}
}
public static void back(int start, int sum, int count) {
if (count == n) {
if (!visit[sum]) {
visit[sum] = true;
cnt++;
}
return;
}
for (int i = start; i < 4; i++) {
back(i, sum + num[i], count + 1);
}
}
}
Reference
この問題について([伯俊]16922号ローマ数字-Java,Java), 我々は、より多くの情報をここで見つけました https://velog.io/@kimmjieun/백준-16922번-로마-숫자-만들기-Java-자바テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol