7-D 질문

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

해결된 질문

작성

안녕하세요 큰돌 님.

7-D를 풀던 도중 메모이제이션 부분에서 질문드립니다.

저는 메모이제이션을 2차원 배열로 하고자 했는데요,

제가 생각하기에

나무가 2개뿐이기에 이동 횟수에 따라 나무의 위치를 특정할 수 있기 때문에

"1번 움직이면 -> 2번 나무, 2번 움직이면 -> 1번 나무"와 같이

이동 횟수와 나머지 연산을 통해 '현재 위치'를 메모이제이션 하지 않아도 된다는 생각이 들었습니다.

때문에 이동 횟수와 현재 시간만 메모이제이션 하고자 했습니다.

혹시 이런 식의 접근으로는 풀 수가 없는 것일까요?

제가 제출한 코드도 첨부 드립니다.

http://boj.kr/7d0a67eaf7b8428e912f596c29a971f1

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 지환님 ㅎㅎ

정말 잘 짜셨네요 ㅎㅎ

그리고 지환님이 하신 방식이 DP입니다. 헤헤...

지환님 코드를 좀 다듬어 봤는데요. 이렇게 하시면 됩니다.

#include <bits/stdc++.h>
using namespace std;

int t, w, ret;
int arr[32][1004];
vector<int> vec;

void go(){ 
    for(int i = 0; i <= w; i++){
        for(int j = 0; j < t; j++){
            int tree_pos = (i % 2) + 1; // 현재 자두의 위치 (i번 움직였다면 어느 나무 아래에 있는가)
            int ja_cnt = (vec[j] == tree_pos) ? 1 : 0; // 현재 초에 떨어지는 자두를 받을 수 있다면 1, 아니면 0

            if(j == 0){
                arr[i][j] = ja_cnt; // 첫 초에는 이전 값이 없으므로 현재 값만 저장
            } else if(i == 0){
                arr[i][j] = arr[i][j-1] + ja_cnt; // 움직이지 않는 경우, 이전 초의 값에 현재 초의 결과를 더함
            } else {
                arr[i][j] = max(arr[i-1][j-1], arr[i][j-1]) + ja_cnt; // 움직이거나, 움직이지 않는 경우 중 최대값 선택 후 현재 초의 결과를 더함
            } 
        }
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t >> w;
    vec.resize(t);
    for(int i = 0; i < t; i++){
        cin >> vec[i]; 
    }

    go(); 

    for(int i = 0; i <= w; i++) {
        ret = max(ret, arr[i][t-1]);  
    }

    cout << ret; 
    return 0;
}

주석도 달아놨습니다. 참고 부탁드립니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

김지환

질문자

하하하 ret의 max를 구하는 for 루프를 2로 고정해놔서 틀리는 거 였군요 ㅎ

왜 안 보였지

감사합니다.

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

7-D 질문