티스토리 뷰

[구글 Codejam] B번 문제 (2016 Round1 B)

목차



이 문제의 이름은 Close Match, 2016 Codejam Round1 B의 B번 문제다.
문제 링크 : https://code.google.com/codejam/contest/11254486/dashboard#s=p1


문제 요약

두 문자열 예를 들어 1?, 2?이 주어진다. ?에 0 ~ 9 사이 숫자를 넣어서 두 수의 차이를 최소로 만드는 값을 출력하면 된다. 이 예시에서는 ?에 각각 9와 0을 넣으면 19와 20을 만들어지고 이 때 두수의 차이가 최소가 된다.

주어지는 두 문자열의 길이는 항상 동일하고 두 수의 차이를 최소로 만드는 여러 개의 답이 존재할 때 이 답들 중 첫번째 수가 가장 작은 답을 출력해야한다.


생각 흐름

Large dataset에서 수의 최대 길이가 18 밖에 안되네? back tracking문제인가? 물음표마다 0~9 다 넣어보면 최대 가지인데 무식하게 다 해보는 방법으로는 안되겠구나..

예시를 보니까 각 자리에서 둘 다 물음표일 때 (0, 0), (9, 0), (0, 9)로 채우고 한 쪽만 물음표일 때 반대편 자리의 값을 대입하니까 차이가 최소가 되네? 그럼 이 경우만 고려하면 될까? 최악의 경우에 이니까 다해봐도 되겠네?

놓친 반례가 없을까? ?10, ?9? 일 때 위 규칙대로 하면 010, 090인데 정답은 110, 090 이네. 그럼 둘다 물음표일 때 (0, 1), (1, 0)도 함께 고려해야하나? 그럼?9, 20처럼 한쪽만 물음표 일 때도 그냥 반대편 값(2)를 대입하면 안되고 19, 20으로 답을 선택해야하네.. 두 상황 다 반대편 수랑 1차이 나는 것도 고려해야 하구나.. 아까 찾은 규칙이 잘못됐구나..

그럼 이 방법으로 코드 쓸까? 이 방법은 최악의 경우에 가지라서 경우가 너무 많아서 8분안에 계산 못하고 코드가 너무 더러울것같다. 구글이 더러운 코드로 풀어야하는 문제를 냈을리가 없는데 다시 생각해보자.


어렵다. 예시에서 찾아낸 규칙으로 고려해야하는 경우의 수를 줄이는 방법으로 풀려고 하는데 찾은 규칙에 반례가 없다는걸 확신 못 하겠다. 이럴 땐 규칙의 근거로 사용할 수 있게 상황에 조건을 붙여서 제한해야한다.

두 수의 차이를 구하는 것에 주목해서 차이를 구할 때 내림 수가 없는 상황, 내림 수가 있는 상황으로 하나의 문제를 제한 조건을 붙인 상황으로 나누어 풀자.

내림 수가 없는 상황이면 50720, 30520의 차이를 구할 때 처럼 크거나 같은 수의 각 자리수가 다른 수의 각 자리수보다 모두 크거나 같아야한다. 즉 ?가 있을 때 차이를 최소로 하려면 두 수를 같게 만들면 된다.

내림 수가 있는 상황이면 작은 수의 ?는 9로 큰 수의 ?는 0으로 채우면 된다.

주어진 문자열에 대해서 0 ~ i-1 자리에서 내림 수가 없고 i번째 자리에서 내림 수가 발생한다고 가정하자. 또 수의 대소에 대한 정보도 알야야 결정할 수 있으므로 대소도 가정하자.


솔루션

  1. 두 수 A, B에 대해 A < B 라고 가정하자.
  2. i-1번째 자리 까지 내림 수가 없고 i번째 자리에서 내림 수가 발생한다고 가정하자.
  3. 0~i-1자리의 ?는 두 수를 같게 만들도록하고 i~N-1자리의 ?는 작은 수는 9, 큰수는 0으로 채운다.
  4. 각 가정에 대해서 두 수를 결정하고 최소값이면 답으로 저장한다.
  5. A, B를 바꿔서 위 과정을 한번 더 진행한다.

코드



정리

규칙을 찾을 때 고려 못한 상황에서 반례가 있을거 같으면 가정을 해서 상황에 제약을 걸고 문제를 쪼개서 풀자.


댓글
댓글쓰기 폼