내가 생각했을때 문제에서 원하는부분
첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.
첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.
내가 이 문제를 보고 생각해본 부분
로마 숫자 값: romanValues 배열에 로마 숫자 I, V, X, L의 값을 저장한다.
이 값들은 조합하여 여러 수를 만들기 위해 사용된다.
사용할 숫자의 개수: n 변수는 사용자가 입력한 로마 숫자의 개수를 저장한다.
이는 조합의 깊이를 결정한다.
서로 다른 합 저장: uniqueSums는 중복된 합을 피하기 위해 HashSet을 사용하여 서로 다른 합의 수를 저장해준다.
입력 처리: BufferedReader를 통해 사용자로부터 로마 숫자의 개수를 입력받는다.
합 계산: findPossibleSums 메소드를 호출하여 백트래킹 방식으로 가능한 합을 계산한다.
이 메소드는 재귀적으로 호출되어 모든 조합을 탐색한다.
결과 출력: 마지막으로 uniqueSums의 크기를 사용하여 서로 다른 합의 개수를 출력한다.
BufferedWriter를 사용하여 출력 버퍼를 비우고 종료한다.
백트래킹 메소드: findPossibleSums 메소드는 현재까지 선택한 로마 숫자의 개수(count), 현재까지의 합계(currentSum), 다음으로 선택할 로마 숫자의 시작 인덱스(startIndex)를 인자로 받아, 모든 가능한 조합을 탐색한다.
N개의 숫자를 선택하게 되면 현재의 합을 uniqueSums에 추가하고, 재귀적으로 다음 숫자를 선택하는 과정을 반복한다.
코드로 구현
package baekjoon.baekjoon_27;
import java.io.*;
import java.util.*;
// 백준 16922번 문제
public class Main989 {
static int[] romanValues = {1, 5, 10, 50}; // 로마 숫자 값
static int n; // 사용할 로마 숫자의 개수
static HashSet<Integer> uniqueSums = new HashSet<>(); // 서로 다른 합을 저장할 HashSet
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine()); // 입력값 처리
// 백트래킹을 통해 가능한 모든 합을 계산
findPossibleSums(0, 0, 0);
bw.write(uniqueSums.size() + "\n"); // 결과 출력
bw.flush();
bw.close();
}
// 백트래킹을 통한 합 계산
public static void findPossibleSums(int count, int currentSum, int startIndex) {
if(count == n) { // N개의 로마 숫자 조합이 완성되면
uniqueSums.add(currentSum); // 현재 합을 HashSet에 추가
return;
}
// 각 로마 숫자를 선택하여 재귀 호출
for(int i = startIndex; i < romanValues.length; i++) {
findPossibleSums(count + 1, currentSum + romanValues[i], i); // 현재 숫자를 더하고 재귀 호출
}
}
}
코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.