글 읽기 - 2342 bottom up 질문

kjuny00 1년 전 0

bottom up으로 풀어보고 싶어서 memo[i][j] 항에서 i는 왼발 *5 + 오른발로 현재 발의 위치 상태를 ,j는 수열중 몇번째 수열을 누르는지를 나타내서 bottom부터 up까지 올려가면서 최저값을 갱신해나갈 생각으로 코드를 짰습니다.

질문게시판에 있는 반례들은 다 통과하는데 어디서 틀리는지 틀렸습니다 가 왜 뜨는지 모르겠어서 반례나 오류 알려주시면 감사드리겠습니다.

감사합니다.

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

vector<int>  su;
int n = 0;
int memo[24][100000] = {0,};

void makemin(int& a, int b){
    if (a == 0)
        a = b;
    else
        a = min(a, b);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int k;
    cin >> k;
    if (k == 0){
        cout << 0;
        return 0;
    }
    while (k != 0){
        n++;
        su.push_back(k);
        cin >> k;
    }
    memo[su[0]][0] = 2;
    int l, r;
    for (int j = 1 ; j < n; j++){
        for (int i = 1; i< 24; i++){
            if (memo[i][j-1] == 0)
                continue;
            l = i/5;
            r = i% 5;
            if (l == su[j] || r == su[j])
                makemin(memo[i][j], memo[i][j-1] + 1);
            else if (l == 0){
                makemin(memo[i+5*su[j]][j], memo[i][j-1] + 2);
                if (abs(r-su[j]) == 2)
                    makemin(memo[su[j]][j], memo[i][j-1] + 4);
                else
                    makemin(memo[su[j]][j], memo[i][j-1] + 3);
            }
            else if (r == 0){
                makemin(memo[i+su[j]][j], memo[i][j-1] + 2);
                if (abs(l-su[j]) == 2)
                    makemin(memo[5*su[j]][j], memo[i][j-1] + 4);
                else
                    makemin(memo[5*su[j]][j], memo[i][j-1] + 3);
            }
            else{
                if (abs(l-su[j]) == 2)
                    makemin(memo[5*su[j] + r][j], memo[i][j-1] + 4);
                else
                    makemin(memo[5*su[j] + r][j], memo[i][j-1] + 3);
                if (abs(r-su[j]) == 2)
                    makemin(memo[su[j] + 5 * l][j], memo[i][j-1] + 4);
                else
                    makemin(memo[su[j] + 5 * l][j], memo[i][j-1] + 3);
            }
        }
    }
    int ret = INT16_MAX;
    for (int i = 1; i < 24; i++){
        if (memo[i][n-1] == 0)
            continue;
        if (memo[i][n-1] < ret)
            ret = memo[i][n-1];
    }

    cout << ret;
    
    return 0;
} 

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2342 bottom up 질문

kjuny00 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말