프로그래머스 에어컨 - C++ 풀이
1. dp(currTemp, t): 현재 시각이 t초이고, 현재 온도가 currTemp일 때 남은 시간동안 쾌적함을 유지하기 위한 최소비용 2. 1도 올리는 경우, 1도 내리는 경우, 희망온도를 현재온도로 유지하는 경우, 아예 끄는 경우 중 비용이 최소인 경우를 선택한다. 1. dp(currTemp, t): 현재 시각이 t초이고, 현재 온도가 currTemp일 때 남은 시간동안 쾌적함을 유지하기 위한 최소비용 dp(currTemp, t)를 위와 같이 정의하자. 2. 1도 올리는 경우, 1도 내리는 경우, 희망온도를 현재온도로 유지하는 경우, 아예 끄는 경우 중 비용이 최소인 경우를 선택한다. 어차피 온도는 1초마다 1씩만 내려가거나 올라갈 수 있다. 따라서 희망온도는 신경쓰지 않아도 된다. 현재 온도가 ..
2023. 9. 7.
프로그래머스 광물 캐기 - C++ 풀이
1. dp(dia, iron, stone, idx) = 곡괭이의 각 개수가 (dia, iron, stone)개일 때 minerals[idx...]를 처리하기 위한 최소 피로도 2. 세 가지 곡괭이를 하나씩 사용해보고 최소 피로도를 갖는 경우를 찾는다. 1. dp(dia, iron, stone, idx) = 곡괭이의 각 개수가 (dia, iron, stone)개일 때 minerals[idx...]를 처리하기 위한 최소 피로도 dp(dia, iron, stone, idx)를 위와 같이 정의하자. 각 곡괭이의 개수는 최대 5개이고, 캐야 하는 광물의 개수는 최대 50개로 매우 작기 때문에 O(MN^3)의 시간복잡도도 충분하다. 기저사례는 곡괭이가 하나도 남지 않거나, 남은 광물이 없는 경우이다. 2. 세 가지..
2023. 9. 5.
백준 9184번 신나는 함수 실행 - C++ 풀이
1. 메모이제이션을 통해 시간을 줄일 수 있다. 2. 재귀 함수를 똑같이 구현하되, 이미 구했던 값이라면 재귀호출을 하지 않고 저장해둔 값을 바로 리턴한다. 1. 메모이제이션을 통해 시간을 줄일 수 있다. 단순한 재귀 호출을 통해 w(a, b, c)를 구할 경우 중복되는 호출이 많아진다. 20 이하의 a, b, c 에 대해서만 구해주면 되므로 총 구해야 하는 함수값은 20^3개 뿐이다. 모든 (a, b, c)에 대해 w(a, b, c) 값을 저장해두자. 2. 재귀 함수를 똑같이 구현하되, 이미 구했던 값이라면 재귀호출을 하지 않고 저장해둔 값을 바로 리턴한다. 재귀 함수를 똑같이 구현하되, 만약 이미 구했던 값이라면 재귀호출을 하지 않고 저장해두었던 값을 바로 리턴해주면 된다. #include #incl..
2023. 9. 4.
