[Python]백준 2492 보석

 

https://www.acmicpc.net/problem/2492

2492번: 보석

<알고리즘을 아직 안배워서, 관련내용은 없습니다>

첫 골드문제 해결이여서 너무 뿌듯해서 블로그를 시작하게 되었다.

실버까지는 어찌저찌되는데, 골드만되면 알고리즘 쓰라고 닥달을...

아직 알고리즘 배우기 전이여서 어찌저찌 해결했다. 너무뿌듯함!ㅋㅋ

아래는 알고리즘 없는 풀이입니다

문제 분석

문제 자체는 사고력 수학책에 나올법한 쉬운 문제이다. 이걸 짜는게 문제지...

이 그림과 같이, 좌표평면 가로와 세로 길이를 주어주고 저 빨간색 네모안에 해당 점들을 최대한 많이 넣으면 된다.

이 문제에서 점들을 금광석이라고 한다.

입력되는 값은:

좌표평면 가로, 좌표평면 세로, 금광석갯수, 빨간 정사각형 한 변의 길이

금광석 x좌표, 금광석y좌표

금광석 x좌표, 금광석y좌표

....

출력해야하는것은:

빨간 정사각형 좌측 상단 꼭짓점 좌표x,y

그때 빨간 정사각형 안에있는(걸치는)금광석 수

조건:빨간 정사각형은 좌표평면을 벗어나면 안됨(걸치는건 ok),빨간 정사각형에 금광석이 걸치면 포함된것으로 생각.

해결과정

dictionary로 좌표를 저장하기로 했다. x,y를 묶어서 저장해야하니까 2차원배열을 쓸까 고민했지만, 딕셔너리를 사용해보기로했다.

문제를 해결한 주요 아이디어는 다음과 같다:

정사각형 좌측상단 X,Y좌표를 maxx,maxy, 금광석 갯수를 maxcount변수로 만들어놓는다. (전부 기본 0 저장)

각 경우마다 count해서, maxcount보다 더 크면 세 변수를 바꿔준다.

1. x값들을 기준으로, 딕셔너리를 오름차순 정렬한다.

2. 오름차순으로 x값들이 정렬되면, 가장 작은 값부터 하나하나 기준을 잡고, 기준~기준+k사이의 금광석 좌표를 구한다.

3. 이 범위 내의 점들의 y값들에 대해서도, 오름차순으로 정렬 후 가장 작은 y값부터 위와 같은 행동을 반복한다.

4. 여기서 범위 내 y값들은 정사각형 안에 있을 수 있다고 판단, count 한다.

5. 마지막에 count를 maxcount와 비교해서 더 크면 기준x와 기준y,maxcount를 바꿔준다

6. 모든 과정을 마치고 출력

(가장 중요!)

1y값들을 다시 정렬하면 x와 y의 쌍이 꼬이는 것 아닌가?라는 의문이 들 수 있다.

그러나, x값의 원하는 범위 내 y값들만 가져왔으므로, y를 재정렬해서 카운트해도 전혀 상관없다. 어차피 주어진x범위 내 점들이므로, y값은 어떻게 되도 상관없다

예를들어, x범위가3~10일때, y는 범위가 5000~5007이여도 상관없다. x가3~10인 점들의 y값들을 재정렬하였기 때문이다.

 

마지막으로 조건에 '빨간 정사각형은 좌표평면을 벗어나면 안됨'에 따라, 벗어나는 경우에 출력x값 y값을 조정해주면된다.

dict_1={}
n,m,t,k=map(int, input().split())
#n=지도 가로, m=지도 세로, t=금광석 수, k=정사각형크기
for i in range(t):
    dict_1[i]=[int(i) for i in input().split()]
#배열에 x,y형으로 저장
#x를 작은것부터 정렬
sortdict=dict(sorted(dict_1.items(), key=lambda item:item[1][0]))
#키값 순서대로 정렬
sortdict={i: v for i,(k,v) in enumerate(sortdict.items(),start=0)}
maxx=0
maxy=0
maxcount=0
for i in range(len(sortdict)):
    temparr=[]
    for j in range(i,len(sortdict)):#x확인
        if sortdict[i][0]+k<=n:#i번째 x에 k더한게 끝을 넘냐마냐 판단
            if sortdict[i][0]+k>=sortdict[j][0]>=sortdict[i][0]:#안넘는경우
                temparr.append(sortdict[j][1])
        else:
            if n>=sortdict[j][0]>=sortdict[i][0]:#넘는경우
                temparr.append(sortdict[j][1])
    temparr=sorted(temparr)#temparr은 y값들이 배열로 저장되어있음. 정렬완료
    temp2=0#실제 광석갯수
    for a in range(len(temparr)):#y확인
        for q in range(a,len(temparr)):
            if temparr[a]+k<=m:#a번째 y에 k더한게 끝을 넘냐마냐 판단(천장끝)
                if temparr[a]<=temparr[q]<=temparr[a]+k:#안넘는경우
                    temp2+=1
            else:
                if m>=temparr[q]>=temparr[a]:#넘는경우
                    temp2+=1
        if temp2>maxcount:
            maxcount=temp2
            maxy=temparr[a]+k
            maxx=sortdict[i][0]
        temp2=0
#maxx랑maxy기준으로 그린 사각형이 테두리를 안넘게 해야함
if maxx+k>n:
    maxx=n-k
if maxy>m:
    maxy=m
print(maxx,maxy)
print(maxcount)