백준 성냥개비 풀이 (1) 썸네일형 리스트형 [백준/Python] 3687번 성냥개비 풀이 문제 해석 문제 풀이 문제 알고리즘 선택 각 숫자별 필요한 성냥개비의 갯수는 아래와 같다 1 2 3 4 5 6 7 8 9 0 2 5 5 4 5 6 3 7 6 6 최대값 2개(1)와 3개(7)이 최소 갯수이며 모든 성냥을 1과 7을 통해 소진 시킬 수 있으며 가장 많은 자리수를 가질 수 있도록 유도할 수 있다. 따라서 최대값은 1과 7을 이용해 단순한 탐욕법 (그리디)로 풀어낼 수 있다. 최소값 브루트 포스로 3,5,9와 같은 숫자를 제외한 모든 숫자로 만들어낸 성냥의 갯수를 이용하려고 했으나 최대값을 고려했을 때 시간 초과가 난다 다시 한 번 17까지 모든 숫자를 계산해보았더니 이전 값에 새로운 자리수(0~9)를 추가하는 형태임을 발견했다. (그러나 6개일 때와 13개일 때와 같이 앞자리에 0이 올 수 .. 이전 1 다음
