(JAVA) 백준 1339번 : 단어 수학

 

https://www.acmicpc.net/problem/1339

1339번: 단어 수학

 

 

 

백트래킹 문제로 해결해야 할 줄 알고

 

했다가

 

시간은 4000ms 까지 치솟아서

 

 

또 다른 해설을 찾던 중 

 

수학 문제로 접근하는 방법을 알게 되었다.

(가장 최고 자리에 높은 숫자를 부여하는 그리디 알고리즘은 예외가 존재하기 때문에 안됨!)

 

 

 

그래서

 

백트래킹 방법 간단히 설명하고, 수학 문제 접근 방법으로 설명을 진행하겠다.

 

 

매커니즘

---

백트래킹 방법은

 

1) 알파벳 26개 이므로 26 길이의 int, boolean 배열 생성

 

2) 사용한 알파벳을 따로 체크

 

3) 알파벳 별 숫자를 부여하는 백트래킹 함수 진행

 

4) 9 ~ 0 (또는 10 - 체크한 길이까지) for문을 진행하며 

  해당 숫자를 넣은 경우와 넣지 않은 경우로 나눠 백트래킹 진행

 

5) 모든 알파벳에 숫자를 부여했을 때, 각 단어의 알파벳을 숫자로 변환

 

6) 변환해서 다 더한 값 중 최댓값을 출력

 

이다. 

 

 

 

반면

수학적 접근 방법은 이렇다.

 

예를 들어

 

input:

2

ABCC

CABB

 

가 있을 때

 

알파벳 별 자리 수만 찾아서 26 길이의 int 배열에 저장하는 것이다. (26인 이유는 A ~ Z까지 있을 수 있으므로)

 

 

ABCC = 1000A + 100B + 10C + 1C

CABB = 1000C + 100A + 10B + 1B

 

 

주어진 문제에서는 모든 단어의 합이 최대인 값만 찾으면 된다고 했으므로

저렇게 주어진 자리 수의 값들을 전부 더하고, 가장 자리수가 큰 알파벳부터 높은 숫자를 순차적으로 부여해주면 되는 것이었다..!!!

 

그럼 계속해서 진행해보자.

 

 

ABCC + CABB = 1100 A + 1011 C + 111 B

 

가 된다.

 

 

그러면 배열에는 이렇게 저장되겠지?

 

index:              0(A)  /  1(B)  /  2(C)  

자리 수의 값:    1100  /  111   /   1011

 

 

 

가장 자리수가 큰 알파벳부터 높은 숫자를 순차적으로 부여하기 위해 배열을 정리하자.  

 

 

index:              0(A)  /  1(C)  /  2(B) 

자리 수의 값:    1100  /  1011  /  111

 

 

이제, 이 순서대로 9, 8, 7 을 부여한 다음, 자리 수의 값과 곱해서 결과를 확인하면 끝!!

 

 

 

 

 

이런 해결 방법을 알게 해주신 굇수님들

 

감사합니다.

 

** 소스코드는 제가 직접 푼 방식이 아니므로 이렇게만 두겠습니다.. 

*** 저 매커니즘대로 코딩하면 끝이에요!