삼각형 위의 최대 경로 수 세기 오답의 원인을 찾기 어렵네요ㅜ

  • 박주현
    박주현

    삼각형 위의 최대 경로 수 세기

    제가 생각한대로 구현을 했음에도 불구하고
    계속해서 오답이 나와 질문 드립니다.

    우선 제가 생각한 알고리즘은

    max 배열에는
    각 자리마다 들어올 수 있는 가장 최대값을 배열 원소로 지정합니다.
    예를 들어
    9
    5 7
    1 3 2
    3 5 5 6
    이 예제라면
    max 배열은 for문을 돌면서

    i가 0 일 때 max는 9 -> 위 과정은 반복문으로 안하고 위에서 초기화
    i가 1 일 때 max는 14, 16
    i가 2 일 때 max는 15, 19, 18
    i가 3 일 때 max는 18, 24, 24, 24

    위 for문이 도는 동안
    count 배열은 max 배열의 원소값에 따라
    값이 더해집니다.
    예를 들어
    max 3과 max 4가 있다면

    if(max[3] > max[4])
     count[4] = count[3];
    
    else if(max[3] == max[4])
     count[4] = count[3] + count[4];
    
    else if(max[3] < max[4])
     count[4] = count[4];
    

    이런 방식입니다.
    count 0 과 count i 의 값은 무조건 1입니다.

    이렇게 2개의 배열의 값을 구한 뒤
    max배열에서 최대값을 찾습니다.
    그 다음에 max 배열에서의 최대값의 원소 자리를 구한 뒤
    그 자리의 count 배열 값들을 합하여 답을 출력합니다.

    아무리 생각해도 어느 부분에서 오답이 나온는지 모르겠습니다.
    혹시 조언을 구할 수 있을까요?? ㅜㅜ

    #include <stdio.h>
    #include <string.h>
    
    unsigned long MostCost(unsigned long*, unsigned long);
    
    int main()
    {
      unsigned long i, j, test, size, len, path;
      unsigned long element[5050];
    
      scanf("%d", &test);
    
      for(i=0; i!=test; i++) {
        scanf("%d", &size);
        len = size*(size+1)/2;
        for(j=0; j!=len; j++) {
          scanf("%d", &element[j]);
        }
        printf("\n");
        path = MostCost(element, size);
        printf("%d\n", path);
      }
    
      return 0;
    }
    
    unsigned long MostCost(unsigned long *element, unsigned long size)
    {
      unsigned long i, j, k=1, temp1, temp2, temp3, temp4, maximum=0, path=0;
      unsigned long max[100] = {0, };
      unsigned long count[100] = {0, };
    
      max[0] = element[0];
      count[0] = 1;
    
      for(i=1; i!=size; i++) {
        for(j=0; j!=i+1; j++) {
          if(j==0) {
        temp1 = max[j];
        temp3 = count[j];
        max[j] += element[k++];
          }
          else if(j==i) {
        max[j] = temp1 + element[k++];
        count[j] = 1;
          }
          else {
        if(temp1 > max[j]) {
          temp2 = max[j];
          max[j] = temp1 + element[k++];
          temp1 = temp2;
          temp4 = count[j];
          count[j] = temp3;
          temp3 = temp4;
        }
        else if(temp1 == max[j]) {
          max[j] += element[k++];
          temp4 = count[j];
          count[j] += temp3;
          temp3 = temp4;
        }
        else {
          temp1 = max[j];
          temp3 = count[j];
          max[j] += element[k++];
        }
          }
        }
      }
    
      for(i=0; i!=size; i++) {
        if(max[i] > maximum)
          maximum = max[i];
      }
    
      for(i=0; i!=size; i++) {
        if(max[i]==maximum)
          path += count[i];
      }
    
      return path;
    }
    

    8년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    아이디어는 맞으신 것 같은데, 구현이 전혀 이해가 되지 않네요. -_-; 문제를 잘못 이해하신 것인가 싶기도 하군요. 최소한 코드를 더 알아보기 쉽게 정리하신 뒤 질문하심이 좋겠습니다.


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