201002 [월간 코드 챌린지 시즌1] 9월 문제-풍선 터트리기 분석

yabmoons.tistory.com/576

[ 프로그래머스 [ 월간코드챌린지 ] 풍선 터트리기 ] (C++)

 

* 코드는 위 사이트를 보고 분석했습니다 그리고 코드를 복사해서 가져오면 안될 것 같아 따로 가져오지 않았습니다

 

- 문제

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을단 1개만 남을 때까지 계속 터트리려고 합니다.

• 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
• 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.

 

-> 반드시 살아남을 수 있는 풍선은 숫자가 가장 작은 풍선이거나 두 개의 풍선만 남은 상태에서 번호가 더 작은 풍선을 터트리는 행위를 1회 쓰게 되면 두번째로 가장 작은 풍선이 반드시 살아남을 수 있는 풍선입니다

 

 

- 코드 분석

구조체(struct BALLON) : 숫자가 쓰여진 풍선이기 때문에 숫자와 인덱스를 가진 풍선 구조체 생성

최소값, 최대값 함수(int Min(int A, int B), int Max(int A, int B)) : 풍선에 쓰여진 숫자가 더 작은지 큰지 비교해야 하기 때문에 최소값, 최대값 함수 생성

bool타입 함수bool Cmp(BALLON A, BALLON B)) : 두 풍선을 비교하여 B가 더 크면 true, 작으면 false를 리턴하는 bool타입 함수 생성(bool Cmp(BALLON A, BALLON B))

solution 함수 :

문제 그대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 리턴하는 함수

return answer + 2; // answer(최종적으로 살아남은 풍선의  개수) + 2(실질적으로 반드시 살아남을 수 있는 풍선 2개)

 

solution 함수안에 쓰이는 vector에 대한 개념이 아직 부족해서 좀 더 공부한 다음에 추가로 정리하도록 하겠습니다