백준[19942] 다이어트 (Python3)
문제 자체는 쉬웠지만, 최적의 경로를 사전 순으로 빠른 것을 출력하란 것 때문에 생각이 좀 필요했던 문제. 하지만, 그렇게 어렵게 생각할 필요는 없는 문제였다. 최적의 답을 찾기 위해, 재료를 순서대로 탐색하며 먹을지, 안 먹을지 결정하면 된다. 즉, 매 순간 2가지 선택지가 있으므로, 2^15만큼의 시간 복잡도가 필요하다. 따라서 백트래킹을 사용해 문제를 풀이했다. 사전 순으로 빠르게 출력하란 것은 내가 첫번째 인덱스부터 탐색을 했다면, 신경쓸 필요가 없다. 왜냐하면, 백트래킹 탐색 순서가 낮은 인덱스부터 차례대로 올라가기 때문이다. 탐색한 경로를 리스트 형태로 관리하면서, 기존보다 적은 비용으로 목표 영양소를 섭취할 수 있다면 기존 값을 교체한다. 백트래킹을 쓰지 않는 경우, 파이썬이라면 i tert..
백준 [1059] 좋은 구간 (Python3)
문제 링크 : https://www.acmicpc.net/problem/1059 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 2번 틀리고 해결한 문제, 이 문제에서 함정이 있는데, 예제만 보고 배열을 구성할 경우 20%에서 틀릴 것이다. 완전 탐색 입력 받은 집합 S를 오름차순 정렬해, N보다 처음으로 값이 큰 위치와 그 전 위치의 값을 각각 A, B라고 하자. 지문 범위에 맞추기 위해 A는 1 더하고, B는 1 뺀다. 만약, 정확히 일치하는 S의 원소가 있다면 0을 출력하고 프로그램을 종료한다. 최소 값이 A 부터 N - 1까지는 지정할 수 있는 최대 범위가 N ~ B이고, 최소 값이 N이면 지정할 수 있는 최대 ..