[ 백준 ] 2346 / 풍선 터뜨리기
# Appreciation
/*
* Problem :: 2346 / 풍선 터뜨리기
*
* Kind :: Simulation
*
* Insight
* - 예제 입력 1
* + 5
* 3 2 1 -3 -1
* # 1번 풍선을 터뜨림, 오른쪽으로 3칸 이동
* x 2 1 -3 -1
* 2 3 4 5 <= 풍선 번호
* 0 1 2 3
* # 4번 풍선을 터뜨림, 왼쪽으로 3칸 이동
* x 2 1 x -1
* 2 3 5
* 2 1 0 3
* # 5번 풍선을 터뜨림, 왼쪽으로 1칸 이동
* x 2 1 x x
* 2 3
* 1 0
* # 3번 풍선을 터뜨림, 오른쪽으로 1칸 이동
* x 2 x x x
* 2
* 1 0
* # 2번 풍선을 터뜨림, 풍선이 더이상 없으므로 종료
*
* - 푸는 방법은 크게 2가지일 것 같다
* + 첫 번째, 터진 풍선의 위치를 저장하기
* # (bool) isDeleted[N] 으로 터진 풍선의 위치를 저장해서
* 터지지 않은 풍선으로 이동할 때만 이동가능한 횟수를 줄여주고
* 이동가능한 횟수가 0 이 되면 멈춘다
* -> 이때 멈춘 자리가 다음에 터뜨릴 풍선의 위치이다
* => 터진 풍선위 위치를 매번 방문해야 되어 비효율적이다
* + 두 번째, 터진 풍선의 위치를 없애버리기
* # Vector 의 erase 연산을 사용해서 터진 풍선의 위치를 없애준다
* Vector 에는 터지지 않은 풍선만 남아있으므로 이동할 때마다 이동가능 횟수가 줄어든다
* -> 이때도 멈춘 자리가 다음에 터뜨릴 풍선의 위치이다
* => 풍선을 터뜨린 위치는 자연스레 1칸 오른쪽의 터지지 않은 풍선의 위치가 된다
* 오른쪽으로 이동해야 되는 경우, 1칸을 이미 이동한 것이 되어버렸기에
* 이를 고려해야 한다
*
* Point
* - 다음 풍선을 터뜨릴 위치를 알아낼 때
* idx %= B.size()
* 로 해서 한참동안 헤맸다...
* + Vector 의 size 연산의 결과는 unsigned long 인데
* idx 가 음수인 경우 이를 양수로 만들어버려서 계속 오답이 나왔던 것이다...
* # 3시간 동안 로직이 틀렸나 싶었는데 이게 문제였다는 것을 알았을 때 느껴졌떤 그 허탈감이란...
* -> 역시 기본기가 중요하다
*/
# Code
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <vector>
using namespace std;
#define endl '\n'
// Set up : Global Variables
struct Balloon { int no, num; };
// Set up : Functions Declaration
/* None */
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
int N; cin >> N;
vector<Balloon> B(N);
for (int i=0; i<N; i++) {
cin >> B[i].num;
B[i].no = i+1;
}
// Process
int idx = 0; /* 풍선을 터뜨릴 위치 */
vector<int> A; /* 터진 풍선의 번호가 저장된 Vector */
while (true) {
int num = B[idx].num; /* 터뜨릴 풍선에 적혀있는 수 */
A.push_back(B[idx].no); /* 터뜨릴 풍선의 번호를 저장 */
B.erase(B.begin()+idx); /* 풍선을 터뜨림 */
if (B.empty()) break; /* 남아있는 풍선이 없다면 종료 */
int s = B.size(); /* 남은 풍선의 개수 */
/* 적혀있는 수가 양수이면, 오른쪽으로 이동해야하는데
* 풍선이 터지면서 현재 위치가 오른쪽으로 1칸 이동한 것이 되어버렸기에
* 이를 고려해주어야 함 */
if (num > 0) num--;
/* 참고로 적혀있는 수가 음수이면, 왼쪽으로 이동해야하는데
* 풍선이 터지면서 현재 위치는 오른쪽으로 1칸 이동한 것이 되어버렸지만
* 왼쪽으로는 0칸 이동한 것이 되어
* 고려치 않아도 상관없음 */
idx += num;
idx %= s;
if (idx < 0) idx += s;
}
// Control : Output
for (int no : A) {
cout << no << ' ';
}
}
// Helper Functions
/* None */
Author And Source
이 문제에 관하여([ 백준 ] 2346 / 풍선 터뜨리기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gglifer/백준-2346-풍선-터뜨리기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/*
* Problem :: 2346 / 풍선 터뜨리기
*
* Kind :: Simulation
*
* Insight
* - 예제 입력 1
* + 5
* 3 2 1 -3 -1
* # 1번 풍선을 터뜨림, 오른쪽으로 3칸 이동
* x 2 1 -3 -1
* 2 3 4 5 <= 풍선 번호
* 0 1 2 3
* # 4번 풍선을 터뜨림, 왼쪽으로 3칸 이동
* x 2 1 x -1
* 2 3 5
* 2 1 0 3
* # 5번 풍선을 터뜨림, 왼쪽으로 1칸 이동
* x 2 1 x x
* 2 3
* 1 0
* # 3번 풍선을 터뜨림, 오른쪽으로 1칸 이동
* x 2 x x x
* 2
* 1 0
* # 2번 풍선을 터뜨림, 풍선이 더이상 없으므로 종료
*
* - 푸는 방법은 크게 2가지일 것 같다
* + 첫 번째, 터진 풍선의 위치를 저장하기
* # (bool) isDeleted[N] 으로 터진 풍선의 위치를 저장해서
* 터지지 않은 풍선으로 이동할 때만 이동가능한 횟수를 줄여주고
* 이동가능한 횟수가 0 이 되면 멈춘다
* -> 이때 멈춘 자리가 다음에 터뜨릴 풍선의 위치이다
* => 터진 풍선위 위치를 매번 방문해야 되어 비효율적이다
* + 두 번째, 터진 풍선의 위치를 없애버리기
* # Vector 의 erase 연산을 사용해서 터진 풍선의 위치를 없애준다
* Vector 에는 터지지 않은 풍선만 남아있으므로 이동할 때마다 이동가능 횟수가 줄어든다
* -> 이때도 멈춘 자리가 다음에 터뜨릴 풍선의 위치이다
* => 풍선을 터뜨린 위치는 자연스레 1칸 오른쪽의 터지지 않은 풍선의 위치가 된다
* 오른쪽으로 이동해야 되는 경우, 1칸을 이미 이동한 것이 되어버렸기에
* 이를 고려해야 한다
*
* Point
* - 다음 풍선을 터뜨릴 위치를 알아낼 때
* idx %= B.size()
* 로 해서 한참동안 헤맸다...
* + Vector 의 size 연산의 결과는 unsigned long 인데
* idx 가 음수인 경우 이를 양수로 만들어버려서 계속 오답이 나왔던 것이다...
* # 3시간 동안 로직이 틀렸나 싶었는데 이게 문제였다는 것을 알았을 때 느껴졌떤 그 허탈감이란...
* -> 역시 기본기가 중요하다
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <vector>
using namespace std;
#define endl '\n'
// Set up : Global Variables
struct Balloon { int no, num; };
// Set up : Functions Declaration
/* None */
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
int N; cin >> N;
vector<Balloon> B(N);
for (int i=0; i<N; i++) {
cin >> B[i].num;
B[i].no = i+1;
}
// Process
int idx = 0; /* 풍선을 터뜨릴 위치 */
vector<int> A; /* 터진 풍선의 번호가 저장된 Vector */
while (true) {
int num = B[idx].num; /* 터뜨릴 풍선에 적혀있는 수 */
A.push_back(B[idx].no); /* 터뜨릴 풍선의 번호를 저장 */
B.erase(B.begin()+idx); /* 풍선을 터뜨림 */
if (B.empty()) break; /* 남아있는 풍선이 없다면 종료 */
int s = B.size(); /* 남은 풍선의 개수 */
/* 적혀있는 수가 양수이면, 오른쪽으로 이동해야하는데
* 풍선이 터지면서 현재 위치가 오른쪽으로 1칸 이동한 것이 되어버렸기에
* 이를 고려해주어야 함 */
if (num > 0) num--;
/* 참고로 적혀있는 수가 음수이면, 왼쪽으로 이동해야하는데
* 풍선이 터지면서 현재 위치는 오른쪽으로 1칸 이동한 것이 되어버렸지만
* 왼쪽으로는 0칸 이동한 것이 되어
* 고려치 않아도 상관없음 */
idx += num;
idx %= s;
if (idx < 0) idx += s;
}
// Control : Output
for (int no : A) {
cout << no << ' ';
}
}
// Helper Functions
/* None */
Author And Source
이 문제에 관하여([ 백준 ] 2346 / 풍선 터뜨리기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gglifer/백준-2346-풍선-터뜨리기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)