so1215   1년 전

제가 생각했던 내용에 대해 먼저 설명하겠습니다.

1. 구조체 정의 : 현 주유소의 리터당 가격 / 다음 주유소까지의 거리(마지막 주유소는 다음 주유소까지의 거리가 0이 되도록 설정했습니다.)

2. 입력된 값을 구조체 배열에 넣은다음 처음부터 다음 주유소까지의 거리가 0이 되는 주유소까지 구조체 배열을 순회합니다.

3. 순회하는 과정에서 cost의 최소값을 찾고 업데이트하며 , 최소값이 업데이트 될 때마다 해당 주유소부터 끝까지의 거리를 0으로 초기화한 후 다음 주유소까지의 거리를 해당 주유소보다 작은 cost가 나오지 않을 때까지 다 더해줍니다.  (작은 cost가 나오면 또다시 초기화 후 거리를 더해감)

4. cost가 최소인 주유소의 인덱스를 저장해 두고 (해당 주유소의 cost) * (해당 주유소부터 끝 도시까지의 거리) 를 sum에 더해주고 해당 인덱스의 다음 주유소 까지의 거리를 0으로 업데이트해 둡니다. (-> 2번 순회과정을 3번에서 찾은 최소 cost의 주유소까지로 한정하기 위해서) 

5. 첫번째 도시의 다음 주유소 까지의 거리가 0으로 업데이트되기 전까지, 즉 첫번째 도시의 cost * 다음 도시까지의 거리를 한 값을 sum에 더해줄때까지 해당 과정을 반복하는 과정을 통해 최종 sum의 값을 얻습니다.

long long이 될 수 있는 변수들은 현재 주유소 리터당 가격과 다음 도시까지의 거리, 총 합(sum)과 해당 주유소에서 마지막 주유소까지의 거리(len)을 설정해 두었습니다. 그럼에도 불구하고 58점이 나오는데 이는 첫번째 두번째 서브테스크까진 가능하고 마지막 서브테스크만 틀린 것이라고 생각합니다. 왜 이런 건지에 관해 설명 부탁드립니다. 

hych0502   1년 전

43줄부터 나오는 이중 반복문때문에 시간초과가 나오는 것 같습니다. 해당 문제는  이중 반복문 없이 풀 수 있습니다.

so1215   1년 전

감사합니다. 방향성을 뒤>앞 에서 앞>뒤로 바꾸니 하나의 while문을 통해 해결할 수 있게 되었습니다.

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