오늘 풀어볼 문제는 백준 16922번 문제 "로마 숫자 만들기" 이다.
이 문제는 실버3 문제이고 브루트 포스 문제이다.
문제
로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.
하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.
실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.
로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.입력
첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.출력
첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.📌첫 번째 시도📌
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[] num = {1, 5, 10, 50};
static boolean[] visit;
static int count = 0;
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine()); // 개수 입력 받기
visit = new boolean[20 * 50 + 1];
bruteforce();
System.out.println(count);
}
private static void bruteforce() {
for(int i=0; i<=n; i++) {
for(int j=0; j<=n-i; j++) {
for(int k=0; k<=n-i-j; k++) {
int l = n-i-j-k;
int sum = i * 1 + j * 5 + k * 10 + l * 50;
if(!visit[sum]) {
visit[sum] = true;
count++;
}
}
}
}
}
}이 문제는 브루트 포스를 이용해서 for문 3개를 가지고 무작위로 그냥 계속 곱해주면 된다.
그리고 중복을 피해주기 위해 visit이라는 boolean 배열을 만들어 이미 이런 값을 만든 적이 있는지 확인을 계속적으로 해주면 된다.
끄으으읕!!
💻 💻 💻