문제 풀이 - 원주율 외우기(java)
풀이
완전 탐색 알고리즘
숫자를 세 자리에서 다섯 자리까지 끊어 읽을 수 있습니다. 1111222인 숫자는 {1111, 222} 혹은 {111, 1222}로 나눌 수 있습니다. 최대 만 자리 숫자까지 입력 받으므로 최소 가지 경우의 난이도의 합을 비교해야 합니다.
메모이제이션의 적용
적절한 완전 탐색 알고리즘을 만들면 메모이제이션으로 이 문제를 해결할 수 있습니다. 이 문제를 푸는 완전 탐색 알고리즘은 주어진 수열을 쪼개는 모든 방법을 하나씩 만들어 보며 그중 난이도의 합이 가장 작은 조합을 찾아냅니다. 각 재귀 함수는 한 번 불릴 때마다 첫 조각의 길이를 하나하나 시도해보며 남은 수열을 재귀적으로 쪼갭니다. 첫 조각의 길이는 3, 4, 5 중의 하나이므로 각 경우마다 하나씩의 부분 문제를 풀어야 합니다. 이때 세 개의 부분 문제에 대한 최적해를 각각 구했다고 하면, 전체 문제의 최적해는 다음 세 경우 중 가장 작은 값이 됩니다.
- 길이 3인 조각의 난이도 + 3글자 빼고 나머지 수열에 대한 최적해
- 길이 4인 조각의 난이도 + 4글자 빼고 나머지 수열에 대한 최적해
- 길이 5인 조각의 난이도 + 5글자 빼고 나머지 수열에 대한 최적해
나머지 수열의 최적해를 구할 때 앞의 부분을 어떤 식으로 쪼갰는지는 중요하지 않습니다. (최적 부분 구조가 성립한다는 뜻입니다.) 따라서 부분 수열의 시작 위치 이 주어졌을 때 최소 난이도를 반환하는 함수 를 다음과 같이 정의할 수 있습니다.
여기서 은 에서 시작하는 길이 인 부분 문자열이고, 는 해당 조각의 난이도를 반환하는 함수라고 합시다. 이 함수는 이 같을 때 항상 같은 값을 반환하므로, 메모이제이션으로 쉽게 최적화할 수 있습니다.
시간 복잡도 분석
위 알고리즘은 최대 개의 부분 문제가 있고, 각 부분 문제를 해결하는 데 최대 세 개의 부분 문제를 봅니다. 따라서 시간 복잡도는 이 됩니다.
구현
import java.util.*;
public class Main {
// 외워야할 숫자
public static String N;
// 캐시
public static int[] cache;
// 답
public static int result;
public static void input(Scanner scanner) {
N = scanner.next();
cache = new int[N.length()];
}
public static void solve() {
result = memorize(0);
}
// 수열 N[begin..]를 외우는 방법 중 난이도의 최소 합을 반환하는 메소드
public static int memorize(int begin) {
// 기저 사례: 수열의 끝에 도달했을 경우
if (begin == N.length()) return 0;
// 메모이제이션
if (cache[begin] != 0) return cache[begin];
cache[begin] = 987654321;
for(int L = 3; L <= 5; L++) {
if (begin + L <= N.length())
cache[begin] = Math.min(cache[begin], memorize(begin + L) + classify(begin, begin + L));
}
return cache[begin];
}
// N[a..b] 구간의 난이도를 반환하는 메소드
public static int classify(int a, int b) {
// 숫자 조각을 가져온다.
String M = N.substring(a, b);
// 첫 글자만으로 이루어진 문자열과 같으면 난이도는 1
if (equalAllChar(M)) return 1;
// 등차수열인지 검사한다.
boolean progressive = true;
for (int i = 0; i < M.length() - 1; i++) {
if (M.charAt(i + 1) - M.charAt(i) != M.charAt(1) - M.charAt(0)){
progressive = false;
}
}
// 등차수열이고 공차가 1 혹은 -1이면 난이도는 2
if (progressive && Math.abs(M.charAt(1) - M.charAt(0)) == 1) return 2;
// 두 수가 번갈아 등장하는지 확인한다.
boolean alternating = true;
for (int i = 0; i < M.length(); i++) {
if (M.charAt(i) != M.charAt(i % 2)) {
alternating = false;
}
}
if (alternating) return 4; // 두 수가 번갈아 등장하면 난이도는 4
if (progressive) return 5; // 공차가 1 아닌 등차수열의 난이도는 5
return 10; // 이 외는 모두 난이도 10
}
// str의 모든 문자가 같으면 true 반환하는 메소드
public static boolean equalAllChar(String str) {
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i - 1) != str.charAt(i)) return false;
}
return true;
}
public static void output() {
System.out.println(result);
}
public static void test() {
System.out.println(N);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int testCase = scanner.nextInt();
for (int i = 0; i < testCase; i++) {
input(scanner);
solve();
output();
}
}
}
회고
Author And Source
이 문제에 관하여(문제 풀이 - 원주율 외우기(java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@qwe910205/문제-풀이-원주율-외우기java
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import java.util.*;
public class Main {
// 외워야할 숫자
public static String N;
// 캐시
public static int[] cache;
// 답
public static int result;
public static void input(Scanner scanner) {
N = scanner.next();
cache = new int[N.length()];
}
public static void solve() {
result = memorize(0);
}
// 수열 N[begin..]를 외우는 방법 중 난이도의 최소 합을 반환하는 메소드
public static int memorize(int begin) {
// 기저 사례: 수열의 끝에 도달했을 경우
if (begin == N.length()) return 0;
// 메모이제이션
if (cache[begin] != 0) return cache[begin];
cache[begin] = 987654321;
for(int L = 3; L <= 5; L++) {
if (begin + L <= N.length())
cache[begin] = Math.min(cache[begin], memorize(begin + L) + classify(begin, begin + L));
}
return cache[begin];
}
// N[a..b] 구간의 난이도를 반환하는 메소드
public static int classify(int a, int b) {
// 숫자 조각을 가져온다.
String M = N.substring(a, b);
// 첫 글자만으로 이루어진 문자열과 같으면 난이도는 1
if (equalAllChar(M)) return 1;
// 등차수열인지 검사한다.
boolean progressive = true;
for (int i = 0; i < M.length() - 1; i++) {
if (M.charAt(i + 1) - M.charAt(i) != M.charAt(1) - M.charAt(0)){
progressive = false;
}
}
// 등차수열이고 공차가 1 혹은 -1이면 난이도는 2
if (progressive && Math.abs(M.charAt(1) - M.charAt(0)) == 1) return 2;
// 두 수가 번갈아 등장하는지 확인한다.
boolean alternating = true;
for (int i = 0; i < M.length(); i++) {
if (M.charAt(i) != M.charAt(i % 2)) {
alternating = false;
}
}
if (alternating) return 4; // 두 수가 번갈아 등장하면 난이도는 4
if (progressive) return 5; // 공차가 1 아닌 등차수열의 난이도는 5
return 10; // 이 외는 모두 난이도 10
}
// str의 모든 문자가 같으면 true 반환하는 메소드
public static boolean equalAllChar(String str) {
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i - 1) != str.charAt(i)) return false;
}
return true;
}
public static void output() {
System.out.println(result);
}
public static void test() {
System.out.println(N);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int testCase = scanner.nextInt();
for (int i = 0; i < testCase; i++) {
input(scanner);
solve();
output();
}
}
}
Author And Source
이 문제에 관하여(문제 풀이 - 원주율 외우기(java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwe910205/문제-풀이-원주율-외우기java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)