백준[10836] 여왕벌 (Python3)
bfs로 풀었다면 시간초과를 받았을 문제 정올 문제답게 관찰이 필요한 문제이다. 문제를 보면 흥미로운 사실을 하나 알 수 있는데 애벌래들의 초기 성장 수치는 오른쪽으로 갈 수록 커진다. 그리고 애벌래들은 왼쪽, 왼쪽 위, 위쪽만 확인한다. 즉, 왼쪽 위보단 위쪽이 위치상으로는 더 오른쪽으로 있기 때문에 그냥 위쪽 값만 보면 된다. 즉, (1, 1)부터 (M, M)까지의 애벌래들은 각각 (0, 1) ~ (0, M)의 애벌래의 성장 수치를 그대로 받는다. 또한, 모든 애벌래의 성장 수치는 첫행, 첫열의 애벌래와 똑같고, 추가로 고려할 사항은 없다. 따라서 첫행, 첫열 애벌래들의 성장 수치를 더한 뒤 나머지 애벌래들은 바로 위쪽 애벌래의 성장 수치 합을 그대로 가져다 쓰면 된다. 더보기 M, N = map(i..
백준[19942] 다이어트 (Python3)
문제 자체는 쉬웠지만, 최적의 경로를 사전 순으로 빠른 것을 출력하란 것 때문에 생각이 좀 필요했던 문제. 하지만, 그렇게 어렵게 생각할 필요는 없는 문제였다. 최적의 답을 찾기 위해, 재료를 순서대로 탐색하며 먹을지, 안 먹을지 결정하면 된다. 즉, 매 순간 2가지 선택지가 있으므로, 2^15만큼의 시간 복잡도가 필요하다. 따라서 백트래킹을 사용해 문제를 풀이했다. 사전 순으로 빠르게 출력하란 것은 내가 첫번째 인덱스부터 탐색을 했다면, 신경쓸 필요가 없다. 왜냐하면, 백트래킹 탐색 순서가 낮은 인덱스부터 차례대로 올라가기 때문이다. 탐색한 경로를 리스트 형태로 관리하면서, 기존보다 적은 비용으로 목표 영양소를 섭취할 수 있다면 기존 값을 교체한다. 백트래킹을 쓰지 않는 경우, 파이썬이라면 i tert..