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

  • 박주현
    박주현

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

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

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

    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;
}

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

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


    7년 전 link

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