snujoon   5년 전

  1. 문제대로 입력을 받고
  2. 1 2 3 4가있다면 
    1. 1, 1+2, 1+2+3, 1+2+3+4
    2. 2, 2+3, 2+3+4
    3. 3, 3+4
    4. 4

를 한 후에

3. 크기순으로 정렬해서 첫번째 배열을 출력하려고 했습니다

하지만 자꾸 컴파일 에러가 납니다 



djm03178   5년 전

resultarr이 너무 커서 그렇습니다. 메모리 제한을 아득히 뛰어넘었을 뿐 아니라 물리적으로 아예 할당이 불가능한 크기입니다.

그리고 코드는 코드 적는 칸에 올려주세요.

snujoon   5년 전

코드부분은 죄송합니다 그렇다면 하나하나 대입하는 방식은 불가능하군요?

djm03178   5년 전

메모리 제한을 빼더라도 지금처럼 모든 경우의 수를 구하는 과정 자체의 시간이 O(N^2)이기 때문에 이 방법으로는 풀 수 없습니다.

게다가 정렬을 하기 위해 버블 소트를 쓰고 있어서 무려 O(N^4)의 시간이 걸리는데, 그러면 최악의 경우에 문제 하나를 해결하는 데에 수천년의 시간이 걸릴 수도 있습니다.

답을 O(N)에 구하는 알고리즘을 생각해 보세요. 가능한 경우의 수를 O(N)에 구할 수 있고, 그 중 최대를 구하는 것 역시 정렬을 쓸 필요 없이 O(N)에 구할 수 있습니다.

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