인프런 커뮤니티 질문&답변

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7주차 개념 DP(Dynamic Programming)

7주차 개념 DP - Q. 큰돌의 사과나무

작성

'큰돌의 사과나무' 문제에서 "큰돌은 처음에는 1번 사과나무 아래에 위치해 있다. "라는 조건이 적혀있습니다.

int main() {

// 생략

// 두 가지 초기 상태(1번 나무에 시작, 2번 나무에 시작) 중 최대 값 출력

cout << max(go(0, 1, m - 1), go(0, 0, m)) << '\n';

// 생략

}

그렇기에 cout << go(0, 0, m) << '\n'; 만 적는게 적절하지 않나? 라는 생각이 들었는데 제가 잘못 생각한걸까요? (0 -> 1번 나무, 1 -> 2번 나무)

퀴즈

51%나 틀려요. 한번 도전해보세요!

동적 계획법(Dynamic Programming)을 적용하기 위한 주요 조건은 무엇일까요?

탐욕적 선택 속성, 최적 부분 구조

최적 부분 구조, 중복되는 부분 문제

중복되는 부분 문제, 결정론적 결과

탐욕적 선택 속성, 메모이제이션

답변 2

지식공유자

네 맞습니다. ㅎㅎ 문제 지문에서

큰돌은 빠르게(1초보다 짧은 시간 안에) 다른 나무로 이동할 수 있다. 그러나 큰돌의 체력은 그리 좋지 않아 많이 움직일 수 없다.

-> 가 있어서 그렇게 코드를 구축해야 합니다.

감사합니다.

질문자

다시 고민을 해보니 제가 잘못생각한게 맞는거 같습니다.

0초일 때 큰돌이가 제자리에서 시작한 경우(go(0, 0, m))와 옆나무로 이동한 경우 (go(0, 1, m - 1))를 모두 고려하기 위함인 것 같은데 의도가 맞을까요?

작성한 질문수