2302. 극장 좌석
문제 개요 한칸씩만 이동할 수 있는 좌석과 고정된 좌석이 존재할 때 가능한 모든 조합 수를 구하는 문제입니다. 문제 접근 방법의 가짓수가 최대 20억개이니 브루트 포스로는 해결할 수 없는 문제입니다. 또한 정수에 최대값이 존재하는 언어의 경우에는 이를 고려하여 타입을 설정해야 합니다. (Java의 경우에는 int) 보통 최대값이 매우 큰 문제는 수학적인 내용이 포함되어 있는 경우가 많기 때문에, 수학적으로 접근해보았습니다. VIP에 의해 분리되는 부분들은 각각 가능한 조합을 가질 수 있습니다. 예를 들어 예제로 주어진 123456789에서 4와 7이 VIP라면 다음과 같이 3개의 부분들로 나누어질 수 있습니다. (123) 4 (56) 7 (89) 각 부분들은 독립적이기 때문에 부분들마다 가능한 조합 수들..
문제풀이/백준
2024. 1. 1. 22:14