728x90
풀이
n개의 티셔츠와 m개의 세일러 카라에 대한 bipertite matching 문제이다.
단, 모든 티셔츠가 모든 세일러 카라에 대한 매칭이 가능한 것이 아니다.
문제에서 주어진 아래의 조건을 만족하는 경우에만 매칭이 가능하다.
하얀 티셔츠의 너비를 정수 w라고 할 때, 여기에 붙일 수 있는 세일러 카라는 두 가지가 있다.
- 너비가 w/2 이상 w×3/4이하인 세일러 카라를 붙일 수 있다.
- 카라가 옷보다 살짝 더 넓게 만들어서 너비가 w 이상 w×5/4 이하인 카라를 붙일 수 있다
티셔츠에 대해 입력받은 세일러 카라의 너비를 위의 조건에 맞게 미리 만들어준다면, 티셔츠별로 살펴봐야 하는 불필요한 카라들이 너무 많아진다.
때문에 일단은 너비만 입력받고, 매칭하는 과정에서 위의 너비에 대한 조건을 만족해 세일러복을 만들 수 있는지 확인해야한다.
모든 방문에 대해 매번 새롭게 방문하는 탐색인 경우, 너비에 대한 조건을 확인해야 하니 함수로 만들어주자.
소스코드
출처
18138번: 리유나는 세일러복을 좋아해
너비가 3인 티셔츠와 너비가 2인 세일러 카라를 붙이고, 너비가 5인 티셔츠에 너비가 5인 세일러 카라를 붙이고 너비가 7인 티셔츠에 너비가 4인 세일러 카라를 붙이고 너비가 10인 티셔츠에 너비
www.acmicpc.net
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 4344] 평균은 넘겠지 [C] (0) | 2023.06.24 |
|---|---|
| [백준 2458] 키 순서 [Python] (0) | 2023.06.24 |
| [백준 21612] Boiling Water [Python] (0) | 2023.06.22 |
| [백준 1647] 도시 분할 계획 [Python] (0) | 2023.06.22 |
| [백준 21631] Checkers [Python] (0) | 2023.06.22 |