smucs13   6일 전


시간초과 안나려면 어떻게 개선해야할까요?

도와주시면 감사하겠습니다

tc 1번 4번은 나오는데

2번 3번은 무한루프를 도는건지 출력이 안됩니다ㅠ

nahwasa   6일 전

분류가 백트래킹이긴하던데 왠지는 잘 모르겠습니다.

그리디에 더 가깝다고 생각되네요.

사실상 dfs가 필요없는 문제입니다.

요지는 N이 최대 10개라는 점 입니다. 그 이상이었으면 풀이가 좀 달랐겠네요.

즉,

AB

B

..(전부 B 하나)

B

아래와 같이 N이 10개 있더라도 무조건 자리수 높은 문자에 높은 수를 주면 됩니다.

A=9, B=8과 A=8, B=9의 결과는 동일하므로

자리수 높은 문자에 높은 수를 주면 N=9이하일 경우 무조건 정답, N=10이더라도 못해도 동일한값이므로 역시 정답입니다.

이걸 힌트로 어떻게 풀이할지 생각해보심 좋을 듯 합니다.

댓글을 작성하려면 로그인해야 합니다.