인프런 커뮤니티 질문&답변
작성한 질문수
이모스 관련 질문
해결된 질문
작성
·
229
1
안녕하세요. 선생님!
백준 17611번 코드를 아래와 같이 작성했는데, 계속 고쳐봐도 "틀렸습니다"만 돌아와서 질문 남깁니다...
코드가 너무 더러워서 최대한 주석을 달아봤는데.. 이해하시는 데 도움이 됐으면 하는 마음입니다 ㅠㅜ
from collections import defaultdict
import sys
input = sys.stdin.readline
# input
n = int(input())
arr = []
min_x, min_y = sys.maxsize, sys.maxsize
dicH, dicV = defaultdict(list), defaultdict(list)
for _ in range(n):
x, y = map(int, input().split()) # 꼭지점 입력
dicH[x].append(y) # 수평으로 선분을 위치한다고 생각하고 그래프를 시계방향으로 90도 돌렸을 때 높이마다 존재하는 선분의 양 꼭지점을 모아둔 리스트
dicV[y].append(x) # 수직으로 선분을 위치한다고 했을 때, 높이마다 존재하는 선분의 양 꼭지점을 모아둔 리스트
min_x, min_y = min(min_x, x), min(min_y, y)
# 높이마다 꼭지점을 정렬
for key in dicH:
dicH[key] = sorted(dicH[key])
for key in dicV:
dicV[key] = sorted(dicV[key])
# 누적합을 할 리스트 생성
prefixX, prefixY = [0 for _ in range(1_000_001)], [0 for _ in range(1_000_001)]
# 이모스 적용
for key in dicH:
length = len(dicH[key]) # 각 높이마다 꼭지점의 개수를 구하고
temp = 0
while temp < length - 1: # 꼭지점을 두 개씩 짝지어 1과 -1 추가
prefixY[dicH[key][temp] - min_y] += 1 # 누적합 리스트에 값을 올바른 위치에 추가하기 위해 min_y를 빼 시작점이 0이 되도록 함
prefixY[dicH[key][temp + 1] - min_y] -= 1
temp += 2 # 완료하면 두 칸 이동
for i in range(1, 1_000_001):
prefixY[i] += prefixY[i - 1]
for key in dicV:
length = len(dicV[key])
temp = 0
while temp < length - 1:
prefixX[dicV[key][temp] - min_x] += 1
prefixX[dicV[key][temp + 1] - min_x] -= 1
temp += 2
for i in range(1, 1_000_001):
prefixX[i] += prefixX[i - 1]
h = max(prefixY)
v = max(prefixX)
print(max(h, v))
답변 2
0
제 정답 코드입니다!
참고 부탁드립니다!
# https://www.acmicpc.net/problem/17611
# 관찰 :
# 수직이동, 수평이동이 반복된다.
# 위로 기둥이 나오면, 이어서 아래로 기둥이 나온다.
# 가장 우측 지점에 도달하면 suffix로 변경된다. ( 하지만 무시해도 계산된다. )
# 개똥벌레 문제랑 동일한 로직이지만, 수직 + 수평 2번 반복된다.
# 아이디어 :
# 먼저 횡이동을 무시하고 모든 기둥을 나열해서 카운팅 해준다.
# -500,000 ~ 500,000
hn = [0]*1001000
wn = [0]*1001000
# 입력을 먼저 받는 방법(o)
# 입력을 받으면서 하는 방법
height = []
width = []
for n in range(int(input())):
x, y = map(int, input().split())
y = y + 500000
x = x + 500000
width.append(x)
height.append(y)
maxW = max(width)
minW = min(width)
maxH = max(height)
minH = min(height)
#마지막줄은 계산하지 못하기 때문에 미리 더해주고 빼준다.
a1, b1 = width[0],width[-2]
a2, b2 = height[0],height[-2]
wn[min(a1,b1)] += 1
wn[max(a1,b1)] -= 1
hn[min(a2,b2)] += 1
hn[max(a2,b2)] -= 1
#반복문을 돌려서 프리픽스를 하기 위해 1과 -1을 더해준다
for i in range(n-1):
# 홀수는 무조건 x값은 동일, y값만 변경된다.
# if i % 2 == 0:
a = min(height[i], height[i+1])
b = max(height[i], height[i+1])
if a != b:
hn[a] += 1
hn[b] -= 1
# 짝수는 반대다!
# if i % 2 == 1:
c = min(width[i], width[i+1])
d = max(width[i], width[i+1])
if c != d:
wn[c] += 1
wn[d] -= 1
#프리픽스 배열을 만든다.
prefix_h = [0]*1001000
prefix_w = [0]*1001000
# 정답을 출력한다.
# answer = 0
for h in range(minH-2, maxH):
prefix_h[h+1] = prefix_h[h] + hn[h+1]
# print("h",prefix_h[h+1])
# answer = max(answer, prefix_h[h+1])
for k in range(minW-2, maxW):
prefix_w[k+1] = prefix_w[k] + wn[k+1]
# print("k",prefix_w[k+1])
# answer = max(answer, prefix_w[k+1])
print(max(max(prefix_h),max(prefix_w)))
0
안녕하세요, 인프런 AI 인턴입니다.
kyg8821님, 백준 17611번 문제에서 “틀렸습니다”가 뜨는 원인을 함께 찾아보겠습니다.
주어진 코드를 분석해보면 이모스 알고리즘을 사용하여 문제를 해결하고자 하셨네요. 이모스 알고리즘은 많은 구간에 대한 누적합을 효율적으로 계산할 때 유용한 방법입니다. 이를 통해 구간별로 선분의 개수를 찾아내 최대를 구하는 문제 해결 방식을 채택하셨습니다.
코드 내에서
- 각 꼭지점을 수직, 수평 선분 리스트에 추가하고,
- 누적합 리스트(prefixX, prefixY)를 생성하여 이모스 알고리즘을 적용하고,
- 각각의 누적합 배열에서 최댓값을 구하여 그 중 더 큰 값을 결과로 출력하고 있습니다.
문제의 조건에 따라 이 같은 풀이 방식이 적합할 수 있으나, “틀렸습니다” 결과가 나타나는 것은 코드 내에 논리적 오류가 존재할 가능성이 있습니다.
오류를 찾기 위해 다음 사항들을 확인해볼 수 있습니다.
- 입력받은 선분 정보가 정확하게 처리되고 있는지,
- 선분의 시작과 끝을 표시할 때 짝지어 처리하고 있는 부분이 올바르게 구현되었는지,
- 누적합을 구할 때 모든 필요한 범위를 고려하고 있는지,
- 수평과 수직 선분의 누적합을 구하는 과정에 예외 사항 없이 올바르게 구현되었는지 확인해보시기 바랍니다.
또한, 테스트 케이스를 몇 가지 예외적인 상황으로 추가하여 제대로 동작하는지 살펴보시고, 선분 정보를 입력받을 때 조건에 맞게 처리하는 부분이 있는지도 재검토해볼 필요가 있습니다.
위 사항들을 면밀히 점검하시고, 그래도 문제를 찾지 못할 경우 해당 강의의 커뮤니티 질문&답변 게시판을 통해 질문하신다면 강사님께서 더욱 상세한 답변을 제공해 주실 수 있을 것입니다.
도움이 필요하시면 언제든 문의해주시고, 앞으로도 알고리즘 공부에 많은 성취가 있기를 바랍니다!