[백준] 2305 자리배치

문제소개

---

2302극장 좌석 문제의 응용 문제라고 생각됩니다. 

극장 좌석을 좌우로 움직여보면 피보나치 수열이라는 것을 금방 알 수 있습니다.

 

2305자리배치 또한 피보나치라는 점을 생각해서 문제에 접근하였습니다.

 

문제해결

---

 

 

 

1

2

3

4

 

 

 

다음과 같이 4개의 좌석이 있으며 그 중에 2번은 자유석입니다. 

자유석을 제외한 좌석은 지정석입니다. 

지정석 표를 산 사람은 해당 지정석, 해당 지정석 좌우 그리고 자유석에 앉을 수 있습니다.

 

예를 들어 3번 지정석을 구매한 사람은 3,4번 그리고 2번에 앉을 수 있습니다.

이러한 조건을 만족하면서 배치할 수 있는 경우의 수를 구하는 문제 입니다.

 

2가지 풀이 방법을 생각해봤습니다.

1) 자유석에 앉는 경우 + 자유석에 앉지 않는 경우

2) 자유석을 기준으로 좌,우 구분하는 경우

저는 2번 방법으로 문제를 해결하였습니다.

 

좌우로 한 칸씩만 이동할 수 있기 때문에 자유석을 기준으로 1번은 3번으로 갈 수 없습니다.

반대로 3,4번은 2번으로 갈 수 없습니다. 그러므로 아래와 같이 2가지 경우를 생각할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

1

2

*

3

4

+

1

*

2

3

4

-

둘다 자유석에 안지 않는 경우

 

 

 

 

 

 

 

 

 

 

둘다 자유석을 앉지 않는 경우가 중복 발생하므로 (- 자유석을 앉지 않는 경우)를 결과 값에서 빼줍니다.

정리하면 다음 문제는 1번이 자유석일 때 경우의 수 문제로 바꿔서 해결할 수 있습니다.

 

 

 

 

 

 

 

1

2

1

2

3

 

 

 

 

 

1

2

3

다음숫자

 

DP[N] = 자유석이 1번일 때 N 좌석까지 앉는 경우의 수라고 하면

자유석이 1번일 때의 추가 되는 다음숫자는 3가지 경우를 생각할 수 있습니다.

1) 지정석에 그대로 앉는경우 ( DP[N-1] )

2) 바로 앞 좌석에 앉는 경우 ( DP[N-2] )

3) 1번 자유석에 앉는 경우 ( 1에서 N-1까지의 피보나치의 합 )

DP[N] = DP[N-1] + DP[N-2] + F[1] + F[2] + ... + F[N-1]

 

정리하면 내용으로 N = 4 , K=2 인 경우의 수는 

답 = DP[2] * 피보나치[2] + 피보나치[1] * DP[3] - 피보나치[1]*피보나치[2]

입니다.

 

하하.. 뭔가 복잡하게 푼 느낌이네요.

 

소스코드