BOJ2811 상범이의 우울

문제

BOJ2811 상범이의 우울
실버V | 백준 2811 | Python3 파이썬 풀이

알고리즘

맨 처음 생각한 알고리즘
1. 맨 뒤에서부터 체크하며 음수가 연속된(우울 기간의) 길이를 카운트
2. 우울 기간이 시작하는(음수 -> 양수) 구간에서 구간의 길이의 2배만큼 꽃을 채움. 이때, 최장 우울 기간의 길이를 저장해놓음
3. 최장 우울 길이가 여러개인데, 꽃을 채울 수 있는 개수는 다 다를 수 있으므로 (이미 채워졌거나, 앞쪽이라 길이가 잘리거나) 최장 우울 기간 중 꽃을 가장 많이 채울 수 있는 개수를 카운트
4. 3번에서 찾은 기간에 꽃을 채움
5. 꽃 리스트에서 꽃의 개수를 카운트해서 출력

하지만, 위 알고리즘은 끝까지 틀렸다고 나온다. 그래서 친구의 도움을 받아, 3번 이후 알고리즘을 수정하였다.

고친 알고리즘
3. 최장 우울 기간 중 꽃을 채울 수 있는 최대 개수를 카운트
4. 꽃을 실제로 채우지 않고, (x2로 채운 꽃 개수 + x3 최대 개수)를 출력

위와 같이 수정하니 정답을 받을 수 있었다.

코드

고민의 흔적 (틀린 코드이다)..

import sys

input = sys.stdin.readline

# 디버깅용 날짜, 꽃 리스트 출력 함수
def printdays():
    for t in table:
        print('%2d' % t, end=' ')

    print()
    for f in flower:
        print('%2d' % f, end=' ')

    print()


N = int(input())

# 날짜별 기분 정보 리스트
table = list(map(int, input().split()))
# 꽃 채우기 리스트 (없으면 0, 꽃이면 1)
flower = [0] * N

length = 0
maxlength = 0

# 날짜 리스트에서 우울 기간 x2 만큼 꽃을 채움
for i in range(N - 1, -1, -1):
    if table[i] < 0:
        length += 1
        continue

    for j in range(0, length * 2):
        if (i - j) > -1:
            flower[i - j] = 1
    
    # 우울 기간 중 최장 기간을 구함
    maxlength = max(maxlength, length)

    length = 0

# printdays()

ans = 0
for f in flower:
    if f == 1:
        ans += 1

# print(ans)

maxidx = 0
maxcount = 0
length = 0

# 최장 우울 기간들 중에서
for i in range(N - 1, -1, -1):
    if table[i] < 0:
        length += 1
        continue
	
    if length == maxlength:
        count = 0
        # 꽃을 가장 많이 채울 수 있는 구간을 찾음
        for j in range(0, length * 3):
            if (i - j) > -1 and flower[i - j] == 0:
                count += 1
		
        # 꽃을 가장 많이 채울 수 있는 기간의 카운트 값
        if count > maxcount:
            maxcount = count
            maxidx = i

    length = 0

# printdays()

# 원래는 최장 우울 기간 중 가장 많이 채울 수 있는 기간에 꽃을 채우고
# for j in range(0, maxlength * 3):
#     if (maxidx - j) > -1:
#         flower[maxidx - j] = 1

# printdays()

# 꽃의 수를 세어서 출력하려 했으나 -> 오답
# ans = 0
# for f in flower:
#     if f == 1:
#         ans += 1

# 최장 우울 기간은 꽃을 채우지 않고, 
# x2 꽃 개수 + 최장 우울 기간 꽃 개수를 합해서 출력
print(ans + maxcount)

깔끔한 정답 코드

import sys

input = sys.stdin.readline

N = int(input())

# 날짜별 기분 정보 리스트
table = list(map(int, input().split()))

# 꽃 채우기 리스트 (없으면 0, 꽃이면 1)
flower = [0] * N

length = 0
maxlength = 0

# 날짜 리스트에서 우울 기간 x2 만큼 꽃을 채움
for i in range(N - 1, -1, -1):
    if table[i] < 0:
        length += 1
        continue

    for j in range(0, length * 2):
        if (i - j) > -1:
            flower[i - j] = 1
    
    # 우울 기간 중 최장 기간을 구함
    maxlength = max(maxlength, length)

    length = 0

ans = 0
for f in flower:
    if f == 1:
        ans += 1

maxidx = 0
maxcount = 0
length = 0

# 최장 우울 기간들 중에서
for i in range(N - 1, -1, -1):
    if table[i] < 0:
        length += 1
        continue
	
    if length == maxlength:
        count = 0
        # 꽃을 가장 많이 채울 수 있는 구간을 찾음
        for j in range(0, length * 3):
            if (i - j) > -1 and flower[i - j] == 0:
                count += 1
		
        # 꽃을 가장 많이 채울 수 있는 기간의 카운트 값
        if count > maxcount:
            maxcount = count
            maxidx = i

    length = 0

print(ans + maxcount)

결과

잘못된 알고리즘으로 접근해 여러 번 틀린 문제
(알고리즘 자체는 맞는 것 같으나, 어디서 구현이 틀린 것 같다)