지금 https://www.acmicpc.net/problem/1339 1399번 단어 수학 풀고있는데
테스트 케이스들은 통과하는데 시간 초과도 아니고 틀렸습니다가 떠서 내가 짠 소스에 반례가 있는 것 같은데 그게 어떤 상황에서 생기는지 잘 모르겠어가지고,, 일단 내가 구현한 아이디어는 이럼
GCF
ACDEB
이렇게 입력이 들어오면 단순하게 생각했을 때 일단 자릿수가 높은 A, C같은 수들이 큰 숫자를 가질수록 합이 클 가능성이 크니까
A > C > G > D > C > E > F > B 이렇게 판단해서 우선 이걸 배열에 넣어둠(숫자를 넣어줘야 하는 알파벳이 얼마나 있나 확인 겸)
그 다음 백트래킹을 통해 9도 넣어보고 8도 넣어보고 7도 넣어보고.. 하되, 우선 A = 9; C = 8; G = 7, ..., B = 2; 처럼 가중치가 높은 순서대로 실행한 다음,
다른 경우를 시도해볼 때 아직 숫자를 적용하지 않은 D, E 이런 글자들에 무조건 9를 넣어서 이게 다 9가 들어가면 지금까지의 합보다 커질 수 있는지로 가지치기를 해서 재귀 횟수를 줄임
그다음 합을 구해서 가장 큰 합을 출력하는 방식으로 구현했는데 어느 부분에서 틀렸는지 잘 감이 안 잡혀가지고 여따 올려봄
코드안봤는데 그냥 읽어보고 든 생각 써보자면 예시에서 a를 9로 바꿨는데 d,e에 무조건 9를 넣는다는게 이해가 안감 두 알파벳은 하나의 숫자로 바꿔지면 안된다고 쓰여있음 / 출현하는 알파벳은 이미 입력에서 10개 이하로 제한되 있을거같음 / 앞에나올수록 우선순위가 크지만 a,e가 같은 자리에 나온다면 그 뒤를 생각해야함 그래서 배열에 넣고 앞에애들부터 큰 수를 하나씩 넣어보는건 좋지 않은거같음 우선순위가 같다가 뒤에서 바뀔수도있어서
두 알파벳은 하나의 숫자로 바꿔지면 안되지만, 그건 그냥 재귀 호출 횟수를 줄이기 위해서임 다른게 다 9로 들어갔는데도 전의 합보다 작으면 그건 어떤 조합이 들어가도 전의 결과보다 작을거아니야 그럼 어차피 그 케이스론 백트래킹 하는게 무의미해지니까 9로 해준거임
앞에 애들부터 큰 수를 넣는거에서 끝나는 게 아니라 작은 수까지 다 시도해주고있음
그럼 맞게 했겠지뭐 로직은 맞는거같음 우선순위 부여해줄 때 출현 위치랑 출현 빈도에 따라 우선순위만 잘 정해주면 문제없을거같음
ㅇㅎ 근데 진짜 반례가 뭘까,,, 일단 말한 방법으로 우선순위 다시 고민해볼게
이런거 잘 출력하나 확인해보셈 AABB ,BB ,BB ,BB ....일 때 언제 B에 우선순위를 더 높게 부여할것인가
풀었음