-문제 : https://www.acmicpc.net/problem/10775
-정답 풀이 :
1번부터 비행기의 게이트 번호 중 빈 게이트에 넣는 것이라 이해해서 완전 탐색을 생각했지만, 이건 당연히 시간초과가 날 것 같아서
다른 풀이를 시도했으나, 5%에서 계속 틀려서 구글링을 했다.
찾아보니 union-find라는 개념을 이용하는데, 아직 정확히 이해가 가지 않았다.
같은 부모(루트)에 대해서 연결하는 것 같은데 이 부분은 좀 더 공부해야할 것 같다
아무튼 정답풀이
import sys
input=sys.stdin.readline
answer=0
g=int(input())
p=int(input())
planes=[]
parent=[i for i in range(g+1)]
for _ in range(p):
planes.append(int(input()))
def find(x):
if parent[x]==x:
return x
parent[x]=find(parent[x])
return parent[x]
for plane in planes: #각 비행기의 게이트 번호
docking=find(plane)
if docking == 0: #도킹할 수 있는 게이트가 없는 경우
break
#해당 비행기와 게이트는 도킹했다는 것을 나타내기 위함
parent[docking]=parent[docking-1]
answer+=1
print(answer)
-삽질한 풀이;;
g=int(input())
p=int(input())
planes=[]
for _ in range(p):
planes.append(int(input()))
planes=[0]+planes
visit=[0]*(g+1)
visit[0]=1
if g==1:
print(1)
else:
i=1
flag=False
while True:
if i==g:
break
for j in range(planes[i],-1,-1):
if visit[j]==0:
visit[j]=1
flag=True
break
if not flag:
break
else:
i+=1
print(sum(visit)-1)
'백준 > Greedy' 카테고리의 다른 글
[그리디/백준] 2405번 : 세 수, 두 M (0) | 2023.05.08 |
---|---|
[그리디/백준] 2812번 : 크게 만들기 (0) | 2022.07.17 |
[그리디/백준] 8980번: 택배(다시) (0) | 2022.07.16 |
[그리디/백준] 2810번: 컵홀더 (0) | 2022.07.16 |
[그리디/백준] 13904번 : 과제(다시) (0) | 2022.07.15 |