새소식

PS/백준

[백준/1671] 상어의 저녁식사 (Python)

  • -

 

Problem : https://www.acmicpc.net/problem/1671

 

1671번: 상어의 저녁식사

어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크

www.acmicpc.net

 

Difficulty : Platinum 3

 

Status : Solved


Time : 00:20:02

 


 

문제 설명

 

더보기

 

어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크거나 같다면 상어 A는 상어 B를 먹을 수 있다. 그러나, 상어들의 왕 김재홍은 상어들이 많이 없어지는 것을 방지하기 위해서 한 상어가 최대 두 개의 상어만 먹을 수 있게 했다. 상어들은 김재홍의 말을 모두 듣는다.

한 상어가 다른 상어를 잡아먹는 동안 나머지 상어들은 상어를 잡아먹을 수 없으며, 이미 잡아먹힌 상어는 다른 상어들을 잡아먹을 수 없다.

N마리 상어의 크기, 속도, 지능이 주어졌을 때, 살아남을 수 있는 상어 수의 최솟값을 구하시오.

 

 

입력 및 출력

 

더보기

입력

 

첫째 줄에 상어의 마리 수 N이 주어진다. 이 값은 50보다 작거나 같은 자연수이다. 둘째 줄부터 각 상어의 크기, 속도, 지능의 정보가 주어진다. 이 값은 2,000,000,000보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄에 살아남을 수 있는 상어 수의 최솟값을 출력한다.

 

입력 예시

 

5
4 5 5
10 10 8
5 7 10
8 7 7
8 10 3

 

출력 예시

 

2

 

 


 

풀이

 

2023.12.09 - [알고리즘 문제/백준] - [백준/11377] 열혈강호 3 (Python)

 

[백준/11377] 열혈강호 3 (Python)

Problem : https://www.acmicpc.net/problem/11377 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번

magentino.tistory.com

2023.12.08 - [알고리즘 문제/백준] - [백준/11376] 열혈강호 2 (Python)

 

[백준/11376] 열혈강호 2 (Python)

Problem : https://www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가

magentino.tistory.com

2023.12.09 - [알고리즘 문제/백준] - [백준/1017] 소수 쌍 (Python)

 

[백준/1017] 소수 쌍 (Python)

Problem : https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다

magentino.tistory.com

 

이분 매칭 특집. 어제도 그저께도 풀었던 문제와 본질적으로는 동일하다. 이미 잡아먹힌 상어는 다른 상어들을 잡아먹을 수 없다는 함정에 빠지지 말자. 모든 매칭을 종료하면, 위상 순으로 잡아먹을 때 최대 상어가 잡아먹히게 되고 최소 상어가 살아남는다.

 

문제는 사이클 발생 여부이다. 크기, 속도, 지능 수치가 서로 같은 둘 이상의 상어는 사이클을 형성하고, 매칭이 올바르게 이루어지지 않게 된다. 즉 이 경우에는 강제로 두 상어간의 위상을 정해 주어야 한다. 이를 테면 인덱스 정보 등으로 모든 상어들이 사이클을 형성하지 않도록 하는 방법이 있겠다.

 

풀이 코드

N = int(input())

sharks = [list(map(int, input().split())) for _ in range(N)]
eatable_list = [list() for _ in range(N)]
eaten = [-1]*N
visited = [False]*N

for i in range(N-1) :
  ia, ib, ic = sharks[i]
  for j in range(i+1, N) :
    ja, jb, jc = sharks[j]
    if ia >= ja and ib >= jb and ic >= jc :
      eatable_list[i].append(j)
    elif ia <= ja and ib <= jb and ic <= jc :
      eatable_list[j].append(i)

def dfs(shark) :
  for other in eatable_list[shark] :
    if eaten[other] == -1 :
      eaten[other] = shark
      return True
  for other in eatable_list[shark] :
    if visited[other] :
      continue
    visited[other] = True
    if dfs(eaten[other]) :
      visited[other] = False
      eaten[other] = shark
      return True
  return False

ans = 0
for i in range(N) :
  if dfs(i) :
    ans += 1
for i in range(N) :
  if dfs(i) :
    ans += 1
print(N - ans)

풀이 완료!

 

Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.