삼각형 위의 최대 경로 수 세기 오답의 원인을 찾기 어렵네요ㅜ 박주현 삼각형 위의 최대 경로 수 세기 제가 생각한대로 구현을 했음에도 불구하고 계속해서 오답이 나와 질문 드립니다. 우선 제가 생각한 알고리즘은 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 아이디어는 맞으신 것 같은데, 구현이 전혀 이해가 되지 않네요. -_-; 문제를 잘못 이해하신 것인가 싶기도 하군요. 최소한 코드를 더 알아보기 쉽게 정리하신 뒤 질문하심이 좋겠습니다. 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
박주현
삼각형 위의 최대 경로 수 세기
제가 생각한대로 구현을 했음에도 불구하고
계속해서 오답이 나와 질문 드립니다.
우선 제가 생각한 알고리즘은
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가 있다면
이런 방식입니다.
count 0 과 count i 의 값은 무조건 1입니다.
이렇게 2개의 배열의 값을 구한 뒤
max배열에서 최대값을 찾습니다.
그 다음에 max 배열에서의 최대값의 원소 자리를 구한 뒤
그 자리의 count 배열 값들을 합하여 답을 출력합니다.
아무리 생각해도 어느 부분에서 오답이 나온는지 모르겠습니다.
혹시 조언을 구할 수 있을까요?? ㅜㅜ
8년 전