문제 분류
: 선택 유무 백트래킹
최근 풀이 : 260418
문제 분석
day를 선택하는 경우, 선택하지 않는 경우 2가지로 분류해서 진행해야 한다.
그래서 점화식을 이렇게 생각함.
그런데 조합이기 때문에 idx를 추가해서 for문으로 돌릴까?
말까? 를 생각했다.
생각을 유연하게
-
굳이 조합에 얽매이지 말고, 문제에 맞게 작성해보면, 이렇다.
-
주의사항
: 마지막 날짜에서 1일 소모되는 경우에 대한 조건식과 그에 대한 자료를 먼저 확보해야 한다. -
1) 초기화
-
2) 종료식
최근 풀이 241126
-
브루트포스 문제이고
해당 day를 선택할 때와 선택하지 않을 때로 분류해서 진행하는 문제이다. -
문제를 쉽게 접근하기 위해서 인덱스를 마음대로 조정하는 것이 편하다.
😴2번째 조건문에서 반환될 때의 max값 어떻게 될지 생각해야 함.
-> 여기서는 res의 값을 갱신하지 않고 있음.
그러니까 예제 1번에서의 1일 -> 4일 -> 5일 -> 7일로 가고 있는 상황임.
7일의 경우, 벡터의 크기를 벗어나므로 그냥 반환함.
이때의 sum은 누적되어 있는 값이 아니다!
재귀 함수안에서 2개의 재귀가 있고, 사용 용도가 다름.
- sum을 합산해 나가는 용도
- 인덱스만 증가하는 용도.
-
그림
-
조건문을 2개 만든 이유
: 문제에서 1day만에 끝날 경우를 생각해서 분류했음.
백트래킹으로 접근하려고 함.
- 맨 처음 코드가 이런식임.
- 조합 푸는것처럼 하려고 했음.
-> 습관만 바꾸면 됨!
🔥🔥🔥