글 읽기 - [Python] 반례를 찾지 못하겠습니다..

durano 6년 전 0

DP로 풀지 않아도 뭔가 될거같아서 최대가 될 수 있는 경우를 찾아봤습니다.

일단 s[0][0](위부터시작)부터 지그재그로 n-2까지 더한 값 = m1 (=>s[0][0]+s[1][1]+s[0][2]+s[1][3]....)

s[1][0](아래부터시작)부터 지그재그로 n-2까지 더한 값 = m2 (=>s[1][0]+s[0][1]+s[1][2]+...)로 설정했습니다.

이제 m1에다가 max(s[0][n-1],s[0][n-2]+s[1][n-1])+m1 를 다시 대입해줍니다. (홀수일 경우 위치반대)

같은방법으로 m2도 구하고 최종적으로 m1과 m2중에 큰 값을 비교해 집어넣었습니다. 올라와있는 예제로는 맞게 나오는데 틀렸다고 하네요 ㅠㅠ 반례좀 부탁드립니다..

for c in range(int(input())):
    n=int(input())
    s=[]
    for _ in range(2):
        s.append([int(x) for x in input().split()])
    m1=0
    m2=0
    for i in range(2):
        for j in range(n-2):
            if i==0 and j%2==0:
                m1+=s[0][j]
                m2+=s[1][j]
            elif i==1 and j%2!=0:
                m1+=s[1][j]
                m2+=s[0][j]
    if n%2:
        m1=max(s[1][n-1],s[1][n-2]+s[0][n-1])+m1
        m2=max(s[0][n-1],s[0][n-2]+s[1][n-1])+m2
    else:
        m1=max(s[0][n-1],s[0][n-2]+s[1][n-1])+m1
        m2=max(s[1][n-1],s[1][n-2]+s[0][n-1])+m2

    print(max(m1,m2))

jh05013 6년 전 6

1
5
1 0 0 0 1
0 0 1 0 0

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

문제

문제

출처

ICPC

[Python] 반례를 찾지 못하겠습니다..

durano 6년 전 0

jh05013 6년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말