plzfday's notes

1463번: 1로 만들기 풀이 스타트링크의 최백준님께서 유튜브에 올리신 DP 강좌를 발견했습니다. 필요하신 분은 보시기 바랍니다. 링크 동적 프로그래밍으로 풀 수 있다. X를 2로 나눌 때, 3으로 나눌 때, 1를 뺄 때의 최소값을 이전 값들을 이용해 계속 업데이트를 해주면 된다 다음 그림과 같이 N = 10일 때 1이 되기 까지의 대략적인 그림을 나타낸 것이다. 문제 해결 방식으로는 2가지가 있다. 10에서 9와 5의 가지를 내릴 수 있는데 사실 이 두 개로는 결과를 도출해 낼 수 없다. 그래서 어쩔 수 없이 각각에 또 다른 뿌리를 내려서 1까지 내려가 얼마나 연산을 해야 하는지 계산할 수 밖에 없다. 이것은 재귀함수로 구현할 수 있는 방식이다.(Top-down) 또 다른 방식으로는 아래서 위로 올라가..

문제 링크설명dp[i]는 i번 것까지 먹었을 때 최댓값.현재 상태 i번째라고 했을 때 점화식 3개현재 것을 먹지 않았을 때 -> dp[i] = dp[i - 1] // i - 1 번째까지 마셨던 것을 업데이트이번 것만 먹을 때(1연속) -> dp[i] = glasses[i] + dp[i - 2] // i - 1 번은 분명히 마시지 않는다.i, i - 1번을 먹을 때(2연속) -> dp[i] = glasses[i] + glasses[i - 1] + dp[i - 3] // i - 2 번은 분명히 마시지 않는다.코드12345678910111213141516171819202122232425262728293031323334#include const int mn = 10001;inline int max(int a, ..

1003번: 피보나치 함수풀이그래프를 그려보면 0과 1이 호출될 때 일정한 규칙이 나오는 것을 알 수 있다. 그래서 dp[i][0]은 i번째 수에서 0의 호출 횟수이고 dp[i][1]은 i번째 수에서 1의 호출 횟수이다.또는 N이 주어질 때 dp[N]은 0의 호출 횟수이고 dp[N+1]은 1의 호출 횟수가 되는데 이 이유는 잘 모르겠다... (아시는 분은 알려주시면 정말 감사드리겠습니다!)코드1번째12345678910111213#include int main(){ int n, k; scanf("%d", &n); for (int j = 0; j

1932번 문제 풀기! 1932번: 숫자삼각형정말 고민을 많이 했는데 생각보다 간단했었따... 이게 왜 DP인지 궁금하신 분들을 위해 설명을 하자면 문제 자체가 위층에서 다음을 위해 적절한 녀석을 골라서 현재 층에서 가장 적절한 녀석을 골라 더해주는 것이다. 좀 깔끔하게 설명하지 못해서 그렇긴 한데 재귀적인 성격이 나오는 문제이다. 문제를 보면 ↘, ↙으로 갈 수 있다고 했다. 이건 위에서 아래로 내려갈 때 가정(1)이고, 아래에서 위로 간다고 가정하면 ↖, ↗으로 갈 수 있다.(2) 개인적으로 이런 문제들은 바텀-업 방식을 사용하는 것을 선호하기 때문에 (2)의 가정이 점화식을 세우기에 좋았다. [1] [2] [3] [4] [5] [1] 7 [2] 3 8 [3] 8 1 0 [4] 2 7 4 4 [5] ..