[BOJ 23847] 백준 23847번 - INU 막대기
| INU 코드페스티벌 2021 풀이 | ||
|---|---|---|
| A | [BOJ 23841] 데칼코마니 | |
| B | [BOJ 23842] 성냥개비 | |
| C | [BOJ 23843] 콘센트 | |
| D | [BOJ 23844] 트리 정리하기 | |
| E | [BOJ 23845] 마트료시카 | |
| G | [BOJ 23847] INU 막대기 | |
| H | [BOJ 23848] 등비수열의 합 |
1. 문제
$23847$. INU 막대기 (INU 코드페스티벌 2021 Open Contest G번)
2. 풀이
IN과 NU, II 막대기가 있으면 하나의 막대기로 만들 수 있다. IN과 NU, UU 막대기가 있으면 UU 하나의 막대기로 만들 수 있다. 이렇듯 어떤 막대기가 있는지 없는지에 따라서 하나의 긴 막대기로 만들 수 있을 수도 없을 수도 있다.
뒤집어서 사용이 가능하므로 II NN UU IN NU UI 총 여섯 종류의 막대기가 있다. 이 막대기들의 존재 여부로 여러 가지 경우를 나누어 판단한다.
IN, NU, UI 막대기 중 세 종류 모두 각각 1개 이상 있다면, 어떠한 막대기라도 모든 막대기를 하나로 이어 붙일 수 있다. 따라서 II NN UU IN NU UI 길이의 총합이 정답이다.
IN, NU, UI 막대기 중 두 종류가 각각 1개 이상 있다면, IN과 NU를 붙이면 IU 즉 UI를 만들 수 있다. 따라서 세 종류의 막대기가 모두 있는 것이나 다름이 없으므로, 바로 위의 경우와 정답이 동일하다.
IN, NU, UI 막대기 중 한 종류만 1개 이상 있다면, 예를 들어 IN만 1개 이상 있다고 해보자. 그럼 II NN UU IN 막대기가 있는 것인데, II NN IN은 연결시킬 수 있지만, UU는 다른 것들과 연결시킬 수 없다. 따라서 II NN IN을 이어 붙인 막대기 하나와 UU를 이어 붙인 막대기 하나, 총 두 개의 막대기가 나오게 된다. 이 두 막대기 중 최댓값이 정답이 된다.
IN, NU, UI 막대기가 모두 없다면, II NN UU 막대기는 서로 연결될 수 없다. 따라서 II NN UU 각각을 이어 붙인 세 막대기 중 최댓값이 정답이 된다.
3. 채점 결과
4. 회고
막대기를 뒤집어 확인하는 것을 깜박하고 빼먹은 채 구현하여 WA를 받았다.
댓글남기기