20055번: 컨베이어 벨트 위의 로봇
길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부
www.acmicpc.net
<풀이>
시뮬레이션 문제이기 때문에 주어진 조건의 순서대로 구현을 하면 된다.......
회전 큐 처럼 로봇과 벨트가 이동해야하기 때문에 deque를 사용했다.
1. 벨트와 로봇을 회전시킨다.
+ n-1칸에 로봇이 존재하면 로봇을 내려줘야함
2. 가장 먼저 올라간 로봇부터 이동할 수 있음 이동시켜줌
-> 즉, 내리는 위치와 가까운 순서부터 다음 칸으로 이동가능한지 체크해줌
-> n-2부터 1까지 이유는 0번에 로봇을 새로 올리기 때문
-> 현 위치에 로봇이 있으며, 다음칸으로 이동할 수 있는 그 자리에 내구도가 있고, 로봇이 없으면 이동
-> 다음칸이 n-1 이면 어처피 걍 빼야함..
3. 로봇을 컨테이너에 올린다
-> 컨테이너 첫번째 0 에만 올릴 수 있음 (대신 0번에 내구도가 있어야하며, 로봇이 없어야함)
4. deque내에 내구도가 0인 컨테이너가 k개 이상인지 체크해주고, 이상이면 while문을 멈춰준다.
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <deque>
using namespace std;
deque<int> dq,robot;
int n,k,num;
int count(){
int cnt = 0;
for(int i=0; i<dq.size(); i++){
if(dq[i]==0) cnt++;
}
return cnt;
}
int main(void){
cin>>n>>k;
for(int i=0; i<2*n; i++){
cin>>num;
dq.push_back(num);
robot.push_back(0);
}
int ans = 0;
while(1){
if(count() >=k) break;
ans++;
//1. 벨트,로봇 회전
dq.push_front(dq.back());
dq.pop_back();
robot.push_front(robot.back());
robot.pop_back();
if(robot[n-1]) robot[n-1]--;
//2. 가장 먼저 올라간 로봇부터 이동
for(int i=n-2; i>=1; i--){
if(robot[i] && dq[i+1]>=1 && robot[i+1]==0){
robot[i]--;
dq[i+1]--;
if(i==n-2) continue;
robot[i+1]++;
}
}
//3. 로봇 올리기 (컨테이너 시작 점 부터)
if(dq[0]>=1 && !robot[0]){
dq[0]--;
robot[0]++;
}
}
cout<<ans<<"\n";
}
16235번: 나무 재테크
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터
www.acmicpc.net
진짜 하루종일 삽질했다ㅠㅠ 시간초과 잡느라 deque도 사용해보고 우선순위 큐도 사용해보고 했는데 계쏙 틀렸습니다 나와서 다시 원점으로 돌아가서 재도전했는데 계쏙 예제가 틀려서 진짜 한 30분정도 계속 잡고 있었는데... 알고보니 summer에서 더하기 인데 빼기를 쳐 하고 있었다 ^^...아주 아찔해.....정말.....잠 못잘뻔 했어...
<풀이>
시뮬레이션 문제이기 때문에 주어진 조건대로 차근차근 구현하면 된다.
1. 봄/여름/가을/겨울 각 조건대로 따로 함수 구현
2. 한 위치에 여러 개의 나무가 들어갈 수 있기 때문에 vector<int> tree[n][n] 형식으로 구현
3. 여름 에서 사용할 죽은 나무를 따로 저장하기 위해 위치와 나이를 담은 구조체 따로 생성
[주요함수]
1. 봄
- 어린 나무가 우선으로 영양분을 먹어야하기 때문에 정렬을 하고 진행
- 조건대로 해당 나무가 나이만큼 영양분 먹을 수 있으면 영양분을 나이만큼 빼주고 나이를 증가
- 영양분 부족하면 바로 죽은 나무에 넣어주고, 해당 나무를 벡터에서 삭제해준다. -> 벡터 사이즈가 작아졌기 때문에 k--가 꼭필요함 !! 이걸로 삽질 오지게 했다...
2. 여름
- 죽은 나무들이 저장된 벡터를 가지고 사용!
- 죽은 나무의 위치와 같은 위치에 죽은 나무의 나이/2한 값을 영양분으로 추가해줌
+ 매번 사용하기 때문에 죽은 나무를 다 사용하고 나면 초기화 필요함
3. 가을
-- 탐색하면서 나무의 나이가 5로 나누어떨어지는 구간에 대해 인접한 8칸의 위치에 아기 나무 (1)을 넣어준다
4. 겨울
- 가장 쉬운 함수 ㅎㅎ..
- 단순히 영양분에다가 초기에 입력받은 추가되는 양분의 양을 더해주면 된다.
-> k번 뒤에 살아있는 나무의 개수 이기 때문에 나무 벡터에 저장된 각 요소의 길이를 더해주면 된다!
- 만약 나무의 나이의 합이라면 값자체를 더하면 된다 ~
오늘안에 풀 수 있어서..정말 다행이야...~
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
int n,m,k;
struct State{
int x,y,age;
State(){}
State(int a, int b, int c){
x =a;
y = b;
age =c;
}
};
vector<int> tree[15][15];
vector<State> dead_tree;
int arr[15][15], nur[15][15];
void spring(){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
sort(tree[i][j].begin(), tree[i][j].end());
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
for(int k=0; k<tree[i][j].size(); k++){
if(arr[i][j] >= tree[i][j][k]){
arr[i][j] -= tree[i][j][k];
tree[i][j][k]++;
}
else{
dead_tree.push_back(State(i,j,tree[i][j][k]));
tree[i][j].erase(tree[i][j].begin()+k);
k--;
}
}
}
}
}
void summer(){
for(int i=0; i<dead_tree.size(); i++){
int x = dead_tree[i].x;
int y = dead_tree[i].y;
arr[x][y] += (dead_tree[i].age/2) ;
}
dead_tree.clear();
}
void fall(){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
for(int k=0; k<tree[i][j].size(); k++){
if(tree[i][j][k]%5 ==0){
for(int h= 0; h<8; h++){
int nx = i + dx[h];
int ny = j + dy[h];
if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
tree[nx][ny].push_back(1);
}
}
}
}
}
}
void winter(){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
arr[i][j] += nur[i][j];
}
}
}
int main(void){
cin>>n>>m>>k;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin>>nur[i][j];
arr[i][j] = 5;
}
}
int x, y, z;
for(int i=0; i<m; i++){
cin>>x>>y>>z;
tree[x-1][y-1].push_back(z);
}
while(k--){
spring();
summer();
fall();
winter();
}
int cnt = 0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cnt += tree[i][j].size();
}
}
cout<<cnt<<"\n";
}
'Algorithm > BOJ' 카테고리의 다른 글
| [ 삼성대비 ] 7일차 (0) | 2021.08.22 |
|---|---|
| [ 삼성대비 ] 6일차 (0) | 2021.08.21 |
| [ 삼성대비 ] 4일차 (0) | 2021.08.19 |
| [ 삼성대비 ] 3일차 (0) | 2021.08.17 |
| [ 삼성대비 ] 2일차 (0) | 2021.08.16 |