<p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">A[N] 라는 배열이 주어진다. </p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">(N은 int, N의 범위는 0~100,000)</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">A배열 각 요소의 값은 -1,000,000,000 ~ 1,000,000,000</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">A배열의 요소는 하나의 도시를 나타내고, A배열 요소의 값은 그 도시의 매력지수이다.</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">당신은 두개의 도시를 여행 할 수 있다.</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">단, 도시간의 간격은 각 각 1매력지수 씩 증가 한다. // 같은 도시를 두 번 여행 해도 된다. 이때 도시간격으로 인한 매력지수는 0이다.</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">예를 들어 A[5]의 매력이 30, A[4]의 매력이 20일 때 두 도시를 여행한다면</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">A[5] + A[4] +(5-4) = 51</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">51이라는 매력지수를 얻게 된다.</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">예를 들어 A[1]의 매력이 30일 때 A[1] 도시를 여행한다면</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">A[1] + A[1] +(1-1) = 60</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">60이라는 매력지수를 얻게 된다.<br></p> <div style="color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></div> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">이때 가장 큰 매력지수를 return 하여라 </p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">라는 문제 입니다.</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">이중 for 문으로 아래와 같이 문제를 풀었는데..... 아마 시간복잡도 때문에 N이 커질수록 걸리는 시간이 오래 걸려서 낮은 점수를 받은것 같습니다.</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> int maxResult = 0;<br></p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> int compare = 0;</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> for(int i=0; i<N.length; i++ ) {</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> for(int j=i+1; j<N.length; j++) {</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> compare = N[i] + N[j] +(j-i);</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> if(maxResult < compare) {</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> maxResult = compare;</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> }</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> }</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> }</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"> return maxResult;</p> <p style="margin:0px 0px 10px;color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></p> <div style="color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></div> <div style="color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;"><br></div> <div style="color:#333333;font-family:'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Malgun Gothic', Dotdum;font-size:14px;">혹시 이중for 문이 아닌 다른 풀이나, 이중 for문 내에서도 시간 복잡도를 줄일 수 있는 방법이 있을까요?</div>
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.