글 읽기 - 사탕 잘 줍는 방법이 있나요??

rnjsxo33 7년 전 0

가로줄을 선택했을떄의 최대값을 먼저 각각 구한뒤,

최대값들을 다시 세로줄로 선택하는 방법을 실행했는데 시간초과가 납니다.

사탕을 어떻게 하면 더 빨리 주울수 있을까요?

#include <iostream>
#include <algorithm>
using namespace std;
 
 
int cache_temp[100002]; int cache_Sum[100002];/*
                                              bool visit[10000] = { 0, };*/
int temp[100002];
int Sum[100002];
int M = 1, N;
int ans_row = 0;
int ans = 0;
 
int openFunc_row(int startIndex, int nowSum) {
    if (nowSum > cache_temp[startIndex]) {
        cache_temp[startIndex] = nowSum;
        if (startIndex + 2 < N)
            openFunc_row(startIndex + 2, nowSum + temp[startIndex + 2]);
        if (startIndex + 3 < N)
            openFunc_row(startIndex + 3, nowSum + temp[startIndex + 3]);
    }
    return 0;
}
 
int openFunc(int startIndex, int nowSum) {
    if (nowSum > cache_Sum[startIndex]) {
        cache_Sum[startIndex] = nowSum;
        if (startIndex + 2 < M)
            openFunc(startIndex + 2, nowSum + Sum[startIndex + 2]);
        if (startIndex + 3 < M)
            openFunc(startIndex + 3, nowSum + Sum[startIndex + 3]);
    }
    return 0;
 
}
int funcgo_row() {
    if (N >= 1)
        openFunc_row(0, temp[0]);
    if (N >= 2)
        openFunc_row(1, temp[1]);
    return 0;
}
 
int funcgo() {
    if (M >= 1)
        openFunc(0, Sum[0]);
    if (M >= 2)
        openFunc(1, Sum[1]);
    return 0;
}
 
int init() {
    ios::sync_with_stdio(false); // 속도 개선
    int tempSum, tempOdd, tempEven;
    bool tt = true;
    while (tt) {
        cin >> M >> N;
 
        if (M == 0 || N == 0) {
            tt = false;
            break;
        }
        for (int i = 0; i < M; ++i)
            cache_Sum[i] = 0;
 
        for (int i = 0; i < M; ++i) {
 
            for (int i = 0; i < N; ++i) {
                cache_temp[i] = 0;
            }
 
            for (int j = 0; j < N; ++j) {
                cin >> temp[j];
            }
 
            funcgo_row();
            Sum[i] = max(cache_temp[N-1], cache_temp[N-2]);
        }
        funcgo();
        cout << max(cache_Sum[M-1], cache_Sum[M-2])<< endl;
 
    }
    return 0;
}
 
int main() {
    init();
    funcgo();
    return 0;
}

crasy111 7년 전 0

일단 1차원 배열로 생각하지 말고 2차원 배열로 했을때 어떻게 점화식이 나올지 생각해보세요.

그 후에 vector를 이용해서 2차원 dp를 하셔도되고 1차원으로 해서 위치 계산을 해서 dp를 하셔도되고요.

가로로 줍는 최대값과 세로로 줍는 최대값을 다 dfs를 이용해서 구하셨는데, 이는 당연히 시간초과가 납니다. 가로나 세로가 최악의 경우 N*1 혹은 1*N이 될 수도 있기때문이죠.

시간복잡도 계산은 정확하게는 모르겠지만, 가로의 경우 각 i행에 대하여, j번째 열에서 +2를 할지, +3을 할지인데, 이게 2개중 한개를 선택하는 꼴이어서 2^x 형태로 시간이 걸릴거같습니다.

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

문제

문제

출처

ICPC

사탕 잘 줍는 방법이 있나요??

rnjsxo33 7년 전 0

crasy111 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말