잡블로그

처음에 접근 방법은 

일렬로 좌석이 배치되어있으므로 

1. 해당 좌석 자리(i)에서 -1칸 (i-1) 칸으로 이동하는 경우

2. 해당 좌석 자리(i)에서 그대로 있는 경우

3. 해당 좌석 자리(i)에서 +1칸 (i+1) 칸으로 이동하는 경우로 생각했었다.

그런데 이경우를 보니 

vip좌석(움직이지 못하는 좌석)을 제외하고 접근하였다. 

vip 좌석이 없는 경우라고 가정하고서 

① 1 만 있는 경우

에는 자기 자리 밖에 못 앉는다. 그러므로 경우의 수는 1 이다.

② 1 2 가 있는 경우

에는 그대로 자기 자리에 앉거나, 둘이 자리를 바꾸는 경우 각각 더해서 2가지 경우가 된다.

③ 1 2 3 이 있는 경우

에는 1을 그대로 두면 ②의 경우가 발생한다. 

이때 2 1 을 바꾸어 앉는 경우가 발생할 수 있으므로, ①의 경우가 발생한다. 

그러므로, ① + ② 의 경우이다.

④ 1 2 3 4 가 있는 경우

1을 그대로 두는 경우 2 3 4 를 바꾸는 경우인 ③ 이 발생한다.

2 1 을 바꾸어 앉으면 ② 의 경우가 발생한다. 

그러므로 ② + ③ 의 경우이다. 

⑤ 1 2 3 4 5 가 있는 경우 

⑤ 의 경우도 마찬가지로 1을 그대로 두는 경우 1, 2를 교환해서 앉는 경우가 발생한다. 

그러므로 ③ + ④ 이다.

결국에는  의 피보나치 공식이었다.

이제 문제의 조건인 vip 좌석(움직이지 못하는 좌석)을 추가 하였다. 

예제로 생각했을 때 

1 2 3 4 5 6 7 8 9 가 있었고, 4와 7의 자리가 vip 좌석이다. 

이런 경우가 되는 것인데, 이때 자리를 스왑할 수 있는 칸이 각 3개, 2개, 2개 있다는 말이다. 

그럼 이때 그 경우들을 곱하면 답이 될 거라고 생각하고 코드 작성했다

이 문제도 BFS로 풀었다. 하 진짜 아무 생각없이 코드를 치나보다 잠을 안자서 그런가 다 핑계겠지 하..

대륙마다 제일 긴 경로를 찾으면, 보물들의 최단거리다. 그냥 맵이 0, 1 로 표시 된다면 대륙이 1 이라면 그 위치부터 뻗어나가 +1 씩 하며 최대 값을 반환해주면 된다.

BFS 하면서 어떤 순서로 +1 씩 시켜줄지 세어진 순서가 일정해야하는 걸 이전 문제를 풀면서 깨달았다;;;;

https://www.acmicpc.net/problem/5585

입력으로 지불할 돈이 주어진다. 

잔돈 = 1000 - 지불한 돈

잔돈(500, 100, 50, 10, 5, 1) 로 교환하여

교환된 총 갯수를 출력하면 되는 문제임.