TRIANGLEPATH 문제를 푸는데 오답이 어디인지 모르겠습니다...

  • nkj36
    nkj36

    TRIANGLEPATH 문제로 아래 답을 제출했는데 어디가 틀린건지 잘 모르겠네요... tri_temp에다가 값을 저장해놓고 아래부터 올라가면서 ㄴ자로 각각 더한 값을 해당 위치에 저장하는 방식으로 풀어보려하는데 고수님들 부탁드립니다!

    #include <iostream>
    using namespace std;
    class tri_st{
        public:
        int tri_temp[100][100];
        tri_st(){
            tri(input_num());
        }
        int input_num(){
            int n,i;
            scanf("%d",&n);
            for(i=0;i<n;i++){
                for(int q=0;q<=i;q++){
                    scanf("%d",&tri_temp[i][q]);
                }
            }
            return i-1;
        }
        int tri(int y){
            for(int i=0;tri_temp[y][i]>=1;i++){
                tri_temp[y][i]=max(tri_temp[y][i]+tri_temp[y+1][i],tri_temp[y][i]+tri_temp[y+1][i+1]);
            }
            if(y==0){
                printf("%d\n",tri_temp[0][0]);
            }
            else{
                tri(y-1);
            }
        }
    };
    int main() {
        int test;
        scanf("%d",&test);
        for(int i=0;i<test;i++){
            tri_st();
        }
        return 0;
    }
    

    7년 전
2개의 댓글이 있습니다.
  • seico75
    seico75
    1. input_num 함수에서 tri_temp 는 0~n-1 줄까지 채워집니다.
      for(i 루프를 나올때는 i = n 이 되기 때문에
      return 값은 n-1 이 되고
      tri 함수는 n-1 부터 돌게 됩니다.
      tri 함수는 y+1 에 있는 두 값을 가져와서 비교하기 때문에
      n 줄에 있는 값부터 계산을 하게 됩니다
      문제에서 주어진 예제는 둘다 n=5 이기 때문데 6번째 줄 값들이 다 0일꺼라서 답은 같으나 n=6 인 test 다음에 n=5인 test 가 오면 6줄에 이전 문제 값이 있어서 답이 틀려집니다.

      해결 방법은 tri_st(input_num()-1)로 수정하거나
      한문제 풀고나서 tri_temp 를 초기화하는 방법이 있겠으나
      당연히 전자를 추천합니다.


2. tri_st(); 는 class 생성자를 호출한건가요?
돌아는가는 것 같은데 이렇게 쓰는 것을 처음봅니다.
3. tri 함수 return 값이 없는데 프로토타입은 int 가 되어 있네요.


7년 전 link
  • nkj36
    nkj36

    덕분에 정답받을수있었습니다 감사합니다~ㅎㅎ
    사실 이 코드를 짤때 이래저래 바꿔가며 시도하다가 아예 생성자를 저렇게 만들어서 코드 수정 번거로움을 좀 덜어보려했습니다!


    7년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.