문제

(주의: 이 문제는 TopCoder 의 번역 문제입니다.)

가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다.

이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다.

이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.

이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:

모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1

숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2

두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4

숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5

그 외의 경우 난이도: 10

원주율의 일부가 입력으로 주어질 때,

난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.

<br/>

입력

12341234 
11111222 
12122222 
22222222 
12673939 
208998628034825342117067982
14808651328230664709384460955058223172535940812848111
74502841027019385211055596446229489549303819644
288109756659334461284756482337867831652
<br/>

출력


4
2
5
2
14
60
99
95
77
<br/>

소스코드


import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class PIAlgo {
	static String input = "19577818577805321712268066130019278766111959092164201989380952572010654858632"; //INPUT
	
	public static final String ID_CASE1 	= "CASE001";
	public static final String ID_CASE2 	= "CASE002";
	public static final String ID_CASE4 	= "CASE004";
	public static final String ID_CASE5 	= "CASE005";
	public static final String ID_CASENOT 	= "CASENOT";

	static int[] numbers = null;
	static boolean[] valid = null;
	
	static List<Point> selected = new ArrayList<>();
	static List<Point> completed = new ArrayList<>();
	
	public static void main(String[] args) {
		numbers = new int[input.length()];
		valid = new boolean[input.length()];
		
		// init
		for (int i = 0; i < input.length(); i++) {
			numbers[i] = Integer.parseInt(input.substring(i, i + 1));
			valid[i] = false;
		}
		
		System.out.println("INPUT LENGTH : " + input.length());

		// CASE SELECT 
		selectionCase1(numbers);
		selectionCase2(numbers);
		selectionCase4(numbers);
		selectionCase5(numbers);
		selectionCaseNot(numbers);
		
		Collections.sort(selected, new XComparator()); //정렬
		print(selected);
		
		// CASE Mix
		List<Point> ps = get(0);
		for(int i=0; i< ps.size();i++) {
			join(ps.get(i));
		}
		
		/* =========================================================*/
		
		Collections.sort(completed, new ValueComparator()); //정렬
		System.out.println("========================");
		print(completed.get(0)); //최소 난이도, 정답
		System.out.println("========================");
	}
	
	public static List<Point> get(int x) {
		List<Point> ps = new ArrayList<>();
		for(int i = 0; i < selected.size(); i++) {
			if(selected.get(i).getX() == x) {
				ps.add(selected.get(i));
			}
		}
		
		return ps;
	}
	
	/* 재귀 */
	public static void join(Point p) {
		int y = p.getY();
		
		Point newP =  null;
		List<Point> ps = get(y + 1);
		Point pp = null;
		
		if(p.getY() == numbers.length -1) {
			p.setCaseId("COMPLETE");
			completed.add(p);
			return;
		}
		
		
		for(int i = 0; i < ps.size(); i++) {
			pp = ps.get(i);
			newP = new Point();
			newP.setCaseId("JOIN " + "[ " + p.getX()+ " , " + p.getY() + " ]\t" + "[ " + pp.getX() + " , " + pp.getY()  + " ]\t");
			newP.setY(pp.getY());
			newP.setValue(p.getValue() + pp.getValue());
			join(newP);
		}
		
	}

	public static void updateValid(int x) {
		valid[x] = true;
	}
	
	/* CASE 1111 : 동일값 */
	private static void selectionCase1(int[] numbers) {
		for (int i = 0; i < numbers.length; i++) {
			if (i + 1 < numbers.length &amp;&amp; numbers[i] == numbers[i + 1]) {
				if (i + 2 < numbers.length &amp;&amp; numbers[i + 1] == numbers[i + 2]) {
					updateValid(i);
					selected.add(new Point(ID_CASE1, i, i + 2, 1));
					if (i + 3 < numbers.length &amp;&amp; numbers[i + 2] == numbers[i + 3]) {
						updateValid(i);
						selected.add(new Point(ID_CASE1, i, i + 3, 1));
						if (i + 4 < numbers.length &amp;&amp; numbers[i + 3] == numbers[i + 4]) {
							updateValid(i);
							selected.add(new Point(ID_CASE1, i, i + 4, 1));
						}
					}
				}
			}
		}
	}

	/* CASE 1234 : 1증가*/
	private static void selectionCase2(int[] numbers) {
		int gap = 0;
		for (int i = 0; i < numbers.length; i++) {
			if (i + 1 < numbers.length) {
				gap = numbers[i + 1] - numbers[i];
				if (i + 2 < numbers.length &amp;&amp; numbers[i + 2] - numbers[i + 1] == 1 &amp;&amp; gap != 0 &amp;&amp; gap == 1) {
					updateValid(i);
					selected.add(new Point(ID_CASE2, i, i + 2, 2));
					if (i + 3 < numbers.length &amp;&amp; numbers[i + 3] - numbers[i + 2] == 1 &amp;&amp; gap != 0 &amp;&amp; gap == 1) {
						updateValid(i);
						selected.add(new Point(ID_CASE2, i, i + 3, 2));
						if (i + 4 < numbers.length &amp;&amp; numbers[i + 4] - numbers[i + 3] == 1 &amp;&amp; gap != 0 &amp;&amp; gap == 1) {
							updateValid(i);
							selected.add(new Point(ID_CASE2, i, i + 4, 2));
						}
					}
				}
			}
		}
	}

	/* CASE 1212 : 반복*/
	private static void selectionCase4(int[] numbers) {
		int a = 0;
		int b = 0;
		for (int i = 0; i < numbers.length; i++) {
			if (i + 1 < numbers.length) {
				a = numbers[i];
				b = numbers[i + 1];
				if (i + 2 < numbers.length &amp;&amp; numbers[i + 2] == a &amp;&amp; numbers[i + 2] - numbers[i + 1] != 0) {
					updateValid(i);
					selected.add(new Point(ID_CASE4, i, i + 2, 4));
					if (i + 3 < numbers.length &amp;&amp; numbers[i + 3] == b &amp;&amp; numbers[i + 3] - numbers[i + 2] != 0) {
						updateValid(i);
						selected.add(new Point(ID_CASE4, i, i + 3, 4));
						if (i + 4 < numbers.length &amp;&amp; numbers[i + 4] == a &amp;&amp; numbers[i + 4] - numbers[i + 3] != 0) {
							updateValid(i);
							selected.add(new Point(ID_CASE4, i, i + 4, 4));
						}
					}
				}
			}
		}
	}

	/* CASE 1357 : 등차 */
	private static void selectionCase5(int[] numbers) {
		int gap = 0;
		
		for (int i = 0; i < numbers.length; i++) {
			if (i + 1 < numbers.length) {
				gap = numbers[i + 1] - numbers[i];
				if (i + 2 < numbers.length &amp;&amp; numbers[i + 2] - numbers[i + 1] == gap &amp;&amp; gap != 0 &amp;&amp; gap != 1) {
					updateValid(i);
					selected.add(new Point(ID_CASE5, i, i + 2, 5));
					if (i + 3 < numbers.length &amp;&amp; numbers[i + 3] - numbers[i + 2] == gap &amp;&amp; gap != 0 &amp;&amp; gap != 1) {
						updateValid(i);
						selected.add(new Point(ID_CASE5, i, i + 3, 5));
						if (i + 4 < numbers.length &amp;&amp; numbers[i + 4] - numbers[i + 3] == gap &amp;&amp; gap != 0 &amp;&amp; gap != 1) {
							updateValid(i);
							selected.add(new Point(ID_CASE5, i, i + 4, 5));
						}
					}
				}
			}
		}
	}
	
	/* 어떤 케이스도 아닌 경우 */
	private static void selectionCaseNot(int[] numbers) {
		for (int i = 0; i < numbers.length; i++) {
			if(valid[i] == false) {
				if(i +2 < numbers.length) { selected.add(new Point(ID_CASENOT, i, i+2, 10)); }
				if(i +3 < numbers.length) { selected.add(new Point(ID_CASENOT, i, i+3, 10)); }
				if(i +4 < numbers.length) { selected.add(new Point(ID_CASENOT, i, i+4, 10));}
			}
		}
	}
	
	/* Print 문 */
	public static void print(Point p) {
		int x = -1;
		int y = -1;
		x = p.getX();
		y = p.getY();
		System.out.print(p.getCaseId() + "\t");
		System.out.print("[ " + x + " , " + y  + " ]\t");
		for (int j = x; j <= y; j++) {
			System.out.print(numbers[j]);
		}
		
		System.out.print("\t VALUE : " + p.getValue());
		System.out.println("");
	}
	
	public static void print(List<Point> selected) {
		int x = -1;
		int y = -1;
		Point  p = null;
		
		for (int i = 0; i < selected.size(); i++) {
			p = selected.get(i);
			x = p.getX();
			y = p.getY();
			System.out.print(p.getCaseId() + "\t");
			System.out.print("[ " + x + " , " + y  + " ]\t");
			for (int j = x; j <= y; j++) {
				System.out.print(numbers[j]);
			}
			
			System.out.print("\t VALUE : " + p.getValue());
			System.out.println("");
		}
	}
}

class XComparator implements Comparator<Point> {
	@Override
	public int compare(Point p1, Point p2) {
		int x1 = p1.getX();
		int x2 = p2.getX();
 
		if (x1 > x2) {
			return 1;
		} else if (x1 < x2) {
			return -1;
		} else {
			return 0;
		}
	}
}

class ValueComparator implements Comparator<Point> {
	@Override
	public int compare(Point p1, Point p2) {
		int x1 = p1.getValue();
		int x2 = p2.getValue();
 
		if (x1 > x2) {
			return 1;
		} else if (x1 < x2) {
			return -1;
		} else {
			return 0;
		}
	}
}

class Point {
	
	String caseId;
	int x;
	int y;
	int value;

	public Point() {
	}
	
	public Point(String caseId, int x, int y, int value) {
		super();
		this.caseId = caseId;
		this.x = x;
		this.y = y;
		this.value = value;
	}

	public String getCaseId() {
		return caseId;
	}

	public void setCaseId(String caseId) {
		this.caseId = caseId;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

}

<br/>

문제풀이

예시를 들어 쉽게 문제풀이를 이해 할 수 있다.

39391237를 예를 들어 보자.

예제는 인덱스 0 ~ 7 까지 8자리의 숫자이다.

우선 각 인덱스로 시작하는 조각을 뽑아 List에 넣어 둔다.

//0번 인덱스 (난이도가 낮은 조각이 있으므로, 보다 큰 난이도의 조각은 뽑지 않는다)
393, 3939


//1번 인덱스 (난이도가 낮은 조각이 있으므로, 보다 큰 난이도의 조각은 뽑지 않는다)
939, 


//2번 인덱스
391, 3912, 39125


//3번 인덱스
912, 9127, 91279


//4번인덱스
127, 1279


//5번인덱스
279

<br/>

다음은 0번 인덱스를 시작으로, 조각들을 이어주는 것이다.

0번 인덱스로 시작하는

**393, 3939 **중 393부터 시작해보자.

393 은 2번 인덱스까지의 숫자이므로 다음으로 3번 인덱스 부터 시작하는 조각을 찾는다.

3번 인덱스를 시작하는 조각은 **912, 9127, 91279 **이다. 조각들을 이어준다. 조각을 이어주며 난이도 숫자도 더 해주자.

**393 912, 393 9127, 393 91279 **세 가지의 조각 조합이 생성된다.

<br/>

그럼 또 다음 조각을 이어보자.

393 912 : 다음에는 조각이 없으므로 예외처리한다.

393 9127 : 다음에는 조각이 없으므로 예외처리한다.

<span style="color:#0000ff">393 91279 : 마지막 인덱스까지 숫자가 나왔으므로, 완성 조합으로 간주. ★

<br/>

<br/>

이제 0번 인덱스로 시작하는

**393, 3939 **중 3939부터 시작해보자.

3939 은 3번 인덱스까지의 숫자이므로 다음으로 4번 인덱스 부터 시작하는 조각을 찾는다.

4번 인덱스로 시작하는 조각은 **127, 1279이다. **조각들을 이어준다. 조각을 이어주며 난이도 숫자도 더 해주자.

3939 127, 3939 1279 두 가지의 조각 조합이 생성된다.

<br/>

그럼 또 다음 조각을 이어보자.

3939 127 : 다음에는 조각이 없으므로 예외처리한다.

<span style="color:#0000ff">3939 1279 : 마지막 인덱스까지 숫자가 나왔으므로, 완성 조합으로 간주. ★

<br/>

<br/>

그럼 이제 모든 완성된 조합을 찾았다.

완성된 조합중 가장 난이도 숫자가 적은 조합을 찾아보자. 정답!

0
이전 댓글 보기
등록
TOP