#15312 : 이름 궁합

풀이방법

사용된 것:

ArrayList

동적 프로그래밍(DP)

 

2022.03.27

문제에 나온 대로 이름점을 보면 되는 문제이다.

이전 단계의 덧셈의 결과가 이번 단계에서 덧셈의 대상이 되기 때문에 동적 프로그래밍 문제라 볼 수 있다.

 

ArrayList<Integer> dp를 사용했다. Vector나 Queue 등을 사용해도 된다.

 

복잡하지 않은 알고리즘이고 코드도 간단하다. 코드를 읽으면 바로 알고리즘을 이해할 수 있다.

그런데 글로 설명하자면 상당히 길다.

귀찮지만, 혹시라도 나 자신이 이 문제의 풀이를 까맣게 잊는다면 다시 읽을 수 있도록... 열심히 설명해보겠다.

 

• 편의를 위한 용어정리

설명의 편의를 위해, 이 글에서는 두 수를 더한 뒤 그 합에 (mod 10) 연산을 하는 것을 '덧셈'이라고 부르겠다.

이 연산에서 더해지는 두 개의 수를 덧셈 대상, 이 연산의 결과를 덧셈 결과라 하겠다.

 

 

그리고 6, 2, 5, 4, 5를 가지고 8, 7, 9, 9를 도출하는 한 차례의 행동을 한 '단계'라고 부르겠다.

 

• 이름점의 특징

이름점은 앞부터 뒤까지 차근차근 순서대로 덧셈을 한다는 특징이 있다.

 

그러므로, 덧셈 대상이 되어야 하는 수들을 dp에 차곡차곡 순서대로 add한 뒤 앞에서부터 더해주면 된다.

덧셈 결과들을 그때그때 dp의 뒷부분에 추가하고,

덧셈 대상으로 쓰인 앞부분의 수들은 다 지워준다.

그럼 dp에는 덧셈 결과들만 남는다.

그걸 그대로 다음 단계에서 덧셈 대상으로 쓰면 된다.

 

• 알고리즘 설명

자세한 방법은 다음과 같다.

 

초기의 dp에는

이름점을 시작할 때 이름A의 철자와 이름B의 철자를 번갈아 적어두듯이,

이름A의 철자들의 획수와 이름B의 철자들의 획수를 번갈아 저장해주면 된다.

 

이름 A가 "CJM"이고 이름 B가 "HER"일 때 dp의 초기 모습:

1

3

2

3

2

2

각각 C의 획수, H의 획수, J의 획수, E의 획수, M의 획수, R의 획수

 

그 후 덧셈을 시작한다.

 

덧셈을 한 번 할 때마다, 덧셈 대상으로서의 역할을 다한 수는 즉시 바로 dp.remove(0)을 통해 지워줄 것이다.

따라서 덧셈은 항상 dp의 첫 번째(인덱스 0)와 두 번째(인덱스 1) 요소끼리 하면 된다.

 

덧셈의 결과값은 덧셈 즉시 dp의 가장 뒤에 add된다.

결과값들이 순서대로 다음 단계에서 덧셈의 대상이 되어야 하기 때문이다.

 

여기서 잠깐!

덧셈의 결과값들이 add되고

덧셈 대상으로서의 역할을 다한 수들은 모두 remove되는데,

모든 단계에서 덧셈에 사용되는 수의 개수보다 덧셈의 결과값의 개수가 정확히 하나 적다.

그 말은 즉, 단계가 거듭될 때마다 dp의 크기가 1씩 줄어든다는 것이다.

이를 이용해 언제 이름점을 종료하면 되는지를 알 수 있다.

dp의 크기가 2가 되면 이름점이 완료된 것이다.

 

dp의 크기가 2가 되었을 때 이름점을 종료하고,

dp에 남아있는 두 개의 수를 차례대로 화면에 출력하면 문제가 해결된다.

 

• 예시

아래는 예시이다.

이름 A가 "CJM"이고 이름 B가 "HER"이다.

빨간 글씨: 이번 단계에서 덧셈 대상이 되는 수
파란 글씨: 이번 단계에서 덧셈 결과로 나온 수


단계 1

1

3

2

3

2

2

위는 dp의 초기 상태​이다.
1과 3을 덧셈하여 4를 도출한 뒤, 역할을 다한 1은 즉시 remove한다.
그럼 dp는 아래와 같이 바뀐다.

3

2

3

2

2

(1+3)%10 = 4

3과 2를 덧셈하여 5를 도출한 뒤, 역할을 다한 3은 즉시 remove한다.

2

3

2

2

4

(3+2)%10 = 5

똑같이 계속해준다.

3

2

2

4

5

(2+3)%10 = 5

2

2

4

5

5

(3+2)%10 = 5

2

4

5

5

5

(2+2)%10 = 4

5번을 모두 하고 나면 dp는 위와 같이 된다. {2, 4, 5, 5, 5, 4}
그런데 가장 앞의 2 또한 역할을 다했다. 2도 remove해준다.

4

5

5

5

4

첫 번째 단계가 완료되었다.
이 dp 배열을 가지고 다음 단계를 똑같이 수행하면 된다.


단계 2

4

5

5

5

4

dp.add((dp.get[0] + dp.get[1]) %10);
dp.remove(0);

5

5

5

4

9

dp.add((dp.get[0] + dp.get[1]) %10);
dp.remove(0);

5

5

4

9

0

dp.add((dp.get[0] + dp.get[1]) %10);
dp.remove(0);

5

4

9

0

0

dp.add((dp.get[0] + dp.get[1]) %10);
dp.remove(0);

4

9

0

0

9

dp.remove(0);

9

0

0

9

덧셈(dp.add((dp.get[0] + dp.get[1]) %10);)은 4번,
없애기(dp.remove(0);)는 5번 해주었다.
이제 {9, 0, 0, 9}를 가지고 단계 3을 수행한다.

...

단계 4까지 끝내주면

9

9

dp가 이렇게 숫자 두 개짜리로 줄어든다.
그럼 완료된 것이다.
99를 화면에 출력하고 종료하면 된다.

 

코드

Java(2022.03.27)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int[] strokes = {3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1};
		
		String A = br.readLine();
		String B = br.readLine();
		
		int len = A.length();
		
		ArrayList<Integer> dp = new ArrayList<Integer>();
		
		//글자들을 번갈아 저장
		for(int i = 0; i<len; i++) {
			dp.add(strokes[A.charAt(i) - 'A']);
			dp.add(strokes[B.charAt(i) - 'A']);
		}
		
		//이름점 보기
		while(true) {
			if(dp.size() == 2)break;
			
			int cur = dp.size();
			
			for(int i = 0; i<cur-1; i++) {
				dp.add((dp.get(0)+dp.get(1))%10);
				dp.remove(0);
			}
			dp.remove(0);
		}
		
		//정답 출력
		System.out.print(dp.get(0));
		System.out.print(dp.get(1));
		
	}

}