글 읽기 - 원소의 합이 가장큰 부분배열 찾기에서 제가 빠트린 케이스가 어떤걸까요?

eventia 4년 전 1

11번째 줄에 아래와 같이 코드를 추가했습니다. 그리고 위의 29번째 줄을 수정했습니다.

런타입에러는 사라졌는데, 결과는 틀렸습니다로 나옵니다.

테스트 케이스로 아래와 같이 8개를 넣어봤고, 모두 제대로 결과가 나오는데 어느 부분에서 놓친게 있는지 잘 모르겠네요.

8개 테스트 케이스는 입력으로 0만 들어오거나 음수만 들어오는 경우와 함께 양수만, 혼합해서 들어오는 경우를 최대한 반영한다고 했는데....

아래와 같이 입력을 주면 출력이 나옵니다. 이 부분까지는 별 문제 없어 보이는데....

[입력]

-5

0 0 0 0

-1 -1 -2

0 0 1

1 1 0 -1 1 1 1 0 1 0

2 2 2 2 2 2 2 2 2 4

0 3 -1 -7 2 9 -1 -1 -1 -1 -1 5 -2 3

[출력]

-5

-1

sum = []
n = int(input())

for i in range(n):
    elementNumber = int(input())

    elements = input().split()
    matrix = []
    for i in range(len(elements)):
        matrix.append(int(elements[i]))

    if max(matrix) < 0 :
        sum.append(max(matrix));
        continue

    matrix.append(-1)
    matrix.insert(0, -1)


    temp = 0
    flag = False
    matrixtemp = []

    for i in range(len(matrix)):
        if ((flag == False) and (matrix[i]>=0)) or ((flag == True) and (matrix[i]<0)) :
            matrixtemp.append(temp)
            temp = 0
            flag = not flag

        if ((flag == False) and (matrix[i]<0)):
            temp = temp + matrix[i]

        elif ((flag == True) and (matrix[i]>=0)):
            temp = temp + matrix[i]


    i = 0
    while((len(matrixtemp) >= 4) and (i*2+3 < len(matrixtemp))) :   # i=0 [1,2,3], 1[3,4,5], 2
        oldSize = len(matrixtemp)
        if (((matrixtemp[i*2+1] + matrixtemp[i*2+2])>= 0) and ((matrixtemp[(i+1)*2+1] + matrixtemp[i*2+2]) >= 0)):
            matrixtemp[i*2+1] = matrixtemp[i*2+1] + matrixtemp[i*2+2] + matrixtemp[i*2+3]
            del matrixtemp[i*2+3]
            del matrixtemp[i*2+2]
        newSize = len(matrixtemp)
        i = i+1

        if (oldSize - newSize > 0 ):
            i = 0

    sum.append(max(matrixtemp));

for i in range (n):
    print(sum[i])

nahwasa 4년 전 0

정확한 답변은 다음분이.. 해주실껍니다!

파이썬 기본문법을 몰라 코드가 정확히 이해가 되지 않으나,

현재까지의 합(temp) 자체를 보시는게 아니고 24줄의 for문을 통해 현재 값에 대해서 따지시는듯 보입니다. 38번째줄 쪽은 아예 이해가 안되구요.. ㄷㄷ

매트릭스 앞뒤로 -1을 붙이신것도 잘 모르겠고..! 파이썬은 i에 대한 반복문 안에서도 i로 계속 서브 반복문을 돌릴 수 있나보군요.. ㄷㄷ

아무튼 제가 코드를 제대로 이해못해 원하시는 답변을 드리진 못하겠으나, 그래도 꽤 오래 찾아보려 노력한김에 뻘댓글이라도 적고 갑니다 ㅠㅠ

일단 이글보고 저도 해본 코드는 아래와 같습니다. (자바)

코드 자체는 제가질문자분의 코드를 이해를 못했으니 제가 해결한 로직만 말씀드리면

전부 음수면 그중 제일 큰수가 답임
아니라면, 0번째부터 우측으로 넣으며 하나 더할때마다 max값과 비교하여 큰 수를 찾음. 그리고, 합이 음수가 되는 인덱스를 x라 할때
배열의 x번째부터 우측으로 넣으며 역시 하나 더할때마다 max값과 비교 / 또 합이 음수가 되는 인덱스를 찾음.
반복
더한 합이 음수가 되면 거기까지의 결과는 무의미하니 그 다음인덱스부터 우측으로만 보면 되므로 그렇게 진행했습니다.

코드에서 합 자체가 아니라 개별값을 보시는듯하여 혹시 로직적으로 저와 비슷하시다면 코드 어딘가가 틀린듯하고,

아니라면 로직을 한번 살펴보시면 좋을 듯 합니다.

좋은 답변 못드려 죄송합니다 ㅠㅠ 파이썬도 좀 익혀보긴해야겠는데.. 파이썬 자체의 코드 스타일은 뭔가 저랑 안맞네요 ㄷㄷ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int TC = Integer.parseInt(br.readLine());
		while (TC-->0) {
			int N = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			int[] arr = new int[N];
			for (int i = 0; i < N; i++)
				arr[i] = Integer.parseInt(st.nextToken());
			int max = Integer.MIN_VALUE;
			for (int i = 0; i < N; i++) {
				if (arr[i] <= 0) {max=max<arr[i]?arr[i]:max;  continue;}
				int sum = arr[i];
				max=max<arr[i]?arr[i]:max;
				for (int j = i+1; j < N; j++) {					
					sum += arr[j];
					if (sum < 0) {i = j; break;}
					max=sum>max?sum:max;
				}
			}
			bw.write(max + "\n");
		}	
		bw.flush();
		br.close();
		bw.close();		
	}
}

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

문제

문제

출처

ICPC

원소의 합이 가장큰 부분배열 찾기에서 제가 빠트린 케이스가 어떤걸까요?

eventia 4년 전 1

nahwasa 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말