[동적계획법] 짜장면, 짬뽕 먹기

 

예제) 철수는 매일 점심마다 짜장면이나 짬뽕을 먹는다. 시험기간이 n일 남았을 때, 철수가 짜장, 짬뽕을 먹는 경우의 수를 구하라. ( 단, 짜장면은 2일, 4일, 6일... 같이 짝수날을 연속으로 먹어야 한다. 또한 짜장면을 먹고 짬뽕을 먹은 뒤 다시 짜장면을 먹을 수 없다. )

 

조건이 까다롭다. 

 

조건1) 짜장면은 2, 4, 6... 연속으로 먹을 수 있다. 

조건2) 짜 → 짬 → 짜 순으로 먹을 수 없다.

 

경우의 수를 따질 때, 동적계획법으로 접근하면 효율적이다. 시험기간 n일을 작은 단위로 분류해야한다. 조건1)은 분류에 적합하다. 예를들어, 시험기간이 8일이 남았다고 해보자.

 

1) 짜장면을 8일 먹은 날

2) 짜장면을 6일 먹은 날

3) 짜장면을 4일 먹은 날

4) 짜장면을 2일 먹은 날

5) 짜장면을 0일 먹은 날

 

이처럼 작은 단위로 분류 할 수 있다. 

 

조건2)는 짜장면의 중복등장을 막는다.  짜 → 짬 → 짜 는 안 된다. 짜장면은 연속으로 한번 먹으면 그걸로 끝이다. 남은 날들은 짬뽕만 먹을 수 있다. 

 

짜장면을 a, 짬뽕을 b라고 하고 시험기간이 8일 남았을 때 경우의 수를 구해보자.

 

1) 짜장면을 8일 먹는 경우

 

 

1가지이다. 

 

2) 짜장면을 6일 먹는 경우 

 

 

 

3가지이다.

 

3) 짜장면을 4일 먹는 경우

 

4가지이다. 

 

이처럼 경우의 수를 구하는 것은 간단하다. 

 

n = 짜장면을 먹은 짝수날

F(n) = 8 - n + 1 이 경우의 수이다.

 

 

1) 짜장면을 8일 먹은 날 (n=8) : 8 - 8 + 1 = 1가지

2) 짜장면을 6일 먹은 날 (n=6) : 8 - 6 + 1 = 3가지

3) 짜장면을 4일 먹은 날 (n=4) : 8 - 4 + 1 = 5가지

4) 짜장면을 2일 먹은 날 (n=2) : 8 - 2 + 1 = 7가지

5) 짜장면을 0일 먹은 날 (n=0) : 8 - 0 + 1 = 9가지 => 1가지 ( 짬뽕만 먹는 날 )

 

총 경우의 수 : 17가지

 

 

 

 

---

 

참고자료

2021년 7기 모집대비 SSAFY(삼성 청년 SW아카데미) SW적성진단 5일 완성