글 읽기 - 자물쇠 질문

zmfldlwl 7년 전 0

냅색 형식으로 풀고있는데

크게 설명드리면

D[i]를 구하기 위해서는 D[i - 1] + i번째 맞추는 횟수, D[i - 2] + (i-1~i) 2글자 맞추는 횟수, D[i - 3] + (i~2 ~ i) 3글자 맞추는 횟수

중에서 최소값을 선택하면서 진행하면 되는거 같은데

N = 3일때 자물쇠를 맞출 수 만 있으면 N이 얼마가 되던지 간에 모두 찾을 수 잇는데

길이가 3인 자물쇠를 어떻게 찾아야할지 ㅠㅠ 방법이 떠오르질 않네요

int main()
{
    scanf("%d %s %s", &N, start, end);

    char aa[5] = { 0, };
    char bb[5] = { 0, };

    for (int i = 0; i < N; i++)
    {
        memset(aa, 0, sizeof(aa));
        memset(bb, 0, sizeof(bb));

        if (i == 0)
        {
            aa[0] = start[0];
            bb[0] = end[0];

            D[i] = mov_count(aa, bb);
        }
        else if (i == 1)
        {
            aa[0] = start[0];
            aa[1] = start[1];

            bb[0] = end[0];
            bb[1] = end[1];
            D[i] = mov_count(aa, bb);
        }
        else
        {
            int r_min = 2100000000;
            //i부터는, D[i - 1] + 1자리(i자리 맞춤), D[i - 2] + (i-1, i자리 맞춤), D[i - 3] + (i - 2, i - 1, i) 자리 맞춤 중에 최소값
            memset(aa, 0, sizeof(aa));
            memset(bb, 0, sizeof(bb));

            aa[0] = start[i];
            bb[0] = end[i];

            int r_t = mov_count(aa, bb);

            r_min = r_min > D[i - 1] + r_t ? D[i - 1] + r_t : r_min;

            memset(aa, 0, sizeof(aa));
            memset(bb, 0, sizeof(bb));

            aa[0] = start[i - 1]; aa[1] = start[i];
            bb[0] = end[i - 1]; bb[1] = end[i];
            
            r_t = mov_count(aa, bb);

            r_min = r_min > D[i - 2] + r_t ? D[i - 2] + r_t : r_min;

            memset(aa, 0, sizeof(aa));
            memset(bb, 0, sizeof(bb));

            aa[0] = start[i - 2]; aa[1] = start[i - 1]; aa[2] = start[i];
            bb[0] = end[i - 2]; bb[1] = end[i - 1]; bb[2] = end[i];
            
            r_t = mov_count(aa, bb);

            r_min = r_min > D[i - 3] + r_t ? D[i - 3] + r_t : r_min;

            D[i] = r_min;
        }
    }

    printf("%d\n", D[N - 1]);

    return 0;
}

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

문제

문제

출처

ICPC

자물쇠 질문

zmfldlwl 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말