BOJ - 풍선 터뜨리기 (2346번)

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

 

배열을 사용하여 풀었습니다.

문제 풀기 전에 어떻게 접근해야할지 공책에 적으면서 했어요.

대략적인 접근 방법은 아래와 같습니다.

/*
	함수를 만들어서 순서가 담긴 벡터를 리턴값으로 했습니다.
    리턴하는 벡터는 이름이 v 입니다.
    
    int tmp = balloons[1];
    v.push_back(1);
    balloons[1] = 0;
    
    while(v.size() != n){
    	if (tmp > 0)
      	  if(현재 인덱스 != n)
        		if(balloons[현재인덱스] != 0)
          		  	tmp--;
           		    현재인덱스++;
          else (현재인덱스 == n)
         		현재 인덱스 = 1;
            	tmp--;
    	else if (tmp < 0)
        	 if(현재 인덱스 != n)
        		if(balloons[현재인덱스] != 0)
          		  	tmp++;
           		    현재인덱스--;
             else (현재인덱스 == 1)
         		현재 인덱스 = n;
            	tmp++;
         else (tmp == 0)
         	tmp = ballons[현재인덱스];
            balloons[현재인덱스] = 0;
            v.push_back(현재인덱스)
    }
*/

 

위의 방법에서 조금 추가해서 적은 게 아래의 소스코드 입니다. 크게 다르지는 않습니다.

차근차근 한 덕분에 한 번에 맞췄네요. 다행입니당.

 

제가 작성한 코드는 아래와 같습니다.

#include <iostream>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
vector<int>func(int n);
int balloons[1001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector <int> result;
	for (int i = 1; i <= n; i++)
		cin >> balloons[i];
	
	result = func(n);
	
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << ' ';
	
	return 0;
}
vector<int> func(int n) {
	vector<int>v;
	int tmp = balloons[1], index = 1; // 첫 시작은 1번 풍선
	v.push_back(1); // 1번을 터뜨림
	balloons[1] = 0; 
	while (v.size() != n) {
		if (tmp > 0) { // 우측으로 가기
			if (index != n) { // 끝 지점인지 확인
				index++;
				if (balloons[index] != 0) {
					// 안 터진 풍선인 경우만 이동 횟수 감소
					tmp--;
				}
				else
					continue;
			}
			else { 
				// 끝지점 일 때
				index = 1; // 맨 왼쪽으로 이동
				if (balloons[index] != 0) {
					// 안 터진 풍선인 경우만 이동 횟수 감소
					tmp--;
				}
				else
					continue;
			}
		}
		else if (tmp < 0) {
			if (index != 1) { // 가장 왼쪽이 아니다.
				index--;
				if (balloons[index] != 0) {
					// 안 터진 풍선인 경우만 이동 횟수 증가 (음수라서)
					tmp++;
				}
				else
					continue;
			}
			else {
				// 가장 왼쪽이다.
				index = n; // 맨 오른쪽으로 이동
				if (balloons[index] != 0) {
					// 안 터진 풍선인 경우만 이동 횟수 증가 (음수라서)
					tmp++;
				}
				else
					continue;
			}
		}
		else { // 풍선을 터뜨려야 하는 위치 tmp == 0
			tmp = balloons[index];
			balloons[index] = 0;
			v.push_back(index);
		}
	}
	return v;
}