PS/SWEA1 [SWEA 1244] 최대 상금 문제 링크 SWEA 1244 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 아이디어 - 전체에서 가장 큰 숫자를 맨 앞자리로 가져오는식으로 그리디라고 생각할 수 있지만 단순히 이런식으로 접근하면 아래의 두 케이스에서 8832라는 답을 동시에 낼 수 없다 2 3288 2 2388 2 따라서 그리디하게 접근 할 시 이것저것 복잡하게 조건을 따져야 할 것 같으므로 - 머리를 비우고 백트래킹으로 완전탐색을 하며 dp로 pruning을 하자 - visit[num][th] : th번 바꾸어서 상금이 num인 상태로 정의하자 그래서 이미 방문 했다면 이후의 값들은 이미 이전에 계산했을테니 재귀를 빠져나간다. 소스코드 #i.. 2020. 8. 11. 이전 1 다음