마쏘's 개발 성장기

문제를 잘 이해해야 한다.

우선 내구도가 떨어지는 경우는 두 가지다.
1) 로봇이 어떤 칸으로 올라갈 때, 올라가려는 칸의 내구도가 감소한다.

2) 로봇이 어떤 칸으로 이동할 때, 이동하려는 칸의 내구도가 감소한다.

로봇을 옮기는 과정은 다음과 같다1) 벨트가 회전한다 rotate()2) 가장 먼저 올라와있던 로봇부터(가장 먼저 올라온 로봇이 아님) 벨트가 회전하는 방향으로 한 칸 이동한다. move()    이때 이동하기 위해서는 이동하려는 칸에 로봇이 없고, 내구도 >= 13) 올라가는 위치(컨베이어 벨트의 처음)에 로봇이 없으면 로봇을 올린다 put_robot()4) 내구도가 0인 칸의 개수가 k개 이상이라면 과정을 종료한다. 그렇지 않다면 1)번으로 돌아간다.

// 20055 컨베이어 벨트 위의 로봇
// https://www.acmicpc.net/problem/20055

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

# include <stdio.h>
# include <iostream>
# include <deque>
using namespace std;

int n = 0, k = 0, step = 0, cnt = 0;
deque <int> belt;
deque<bool> robot;

void rotation() {
	belt.push_front(belt.back());
	belt.pop_back();

	robot.push_front(robot.back());
	robot.pop_back();
}

void move() {
	for (int i = n-2; i >= 0; i--){
		if(robot[i] && !robot[i+1] && belt[i+1] >= 1){
			robot[i] = false;
			robot[i+1] = true;
			belt[i + 1]--;
		}
	}
}

void put_robot() {
	if(belt[0]>0) {
		belt[0]--;		robot[0]=true;
	}	
}

int get_zero_cnt(){
	int zero = 0;
	for (int i = 0; i < 2*n; i++){
		if(belt[i]==0)
			zero++;
	}
	return zero;
}

int main(void){
	cin >> n >> k;

	for (int i = 0; i < 2 * n; i++){
		int val;
		cin >> val;
		belt.push_back(val);
		robot.push_back(false);
	}
	while(true){
		step += 1;
		rotation();
		robot[n - 1] = false;
		move();
		robot[n - 1] = false;
		put_robot();
		if(get_zero_cnt() >= k){
			cout << step << "\n";
			return 0;
		}
	}
	return 0;
}

원래는 que를 사용했는데 먼저 올라와 있던 로봇을 먼저 옮겨야 하는 걸 알게 되고나서 deque로 변경하였다.

참고한 블로그가 있는데 너무 설명이 잘 되어있어서 감사하게 공부했다!

deque 아이디어만 얻고 혼자 짜보고 확인했는데 나름 내 코드로 체화된 것 같아서 기쁘다!!

ssinee.tistory.com/entry/%EB%B0%B1%EC%A4%80-20055%EB%B2%88-%EC%BB%A8%EB%B2%A0%EC%9D%B4%EC%96%B4-%EB%B2%A8%ED%8A%B8-%EC%9C%84%EC%9D%98-%EB%A1%9C%EB%B4%87-%EC%82%BC%EC%84%B1-%EA%B8%B0%EC%B6%9C

입력)

- 10개의 테스트 케이스

- 100x100 크기의 2차원 정수 배열

출력)

-  출력값이 integer 범위를 넘지 않음!

- #(테스트 케이스 번호) (각 행의 합, 각 열의 합, 각 대각선의 합 중 최댓값)

입, 출력 분석)

- (생략)

핵심)

- for문을 잘 다룰 수 있는 능력만 있다면 충분히 할 수 있다.

예시 분석)

- (생략)

실수) 

- 대각선 / 부분에서 x index는 증가하고, y index만 99(100아님!)에서 감소한다는 것

구현)

#include<stdio.h>
using namespace std;

#define SIZE 100
int arr[SIZE][SIZE] = {0,};
int MAX = 0;

int main(int argc, char** argv) {
	int test_case;
	for (test_case = 1; test_case <= 10; ++test_case) {
		MAX = 0;
		scanf("%d", &test_case);
		for (int i = 0; i < SIZE; i++){
			int temp = 0;
			for (int j = 0; j < SIZE; j++){
				scanf("%d", &arr[i][j]);
				temp += arr[i][j]; // 각 행의 합
			}
			if(MAX < temp) MAX = temp;
		}
		for (int j = 0; j < SIZE; j++){
			int temp = 0;
			for (int i = 0; i < SIZE; i++)
				temp += arr[i][j]; // 각 열의 합
			if(MAX < temp) MAX = temp;
		}
		int temp1 = 0, temp2 = 0;
		for (int i = 0; i < SIZE; i++){
			temp1 += arr[i][i];
			temp2 += arr[i][(SIZE-1)-i]; // 실수한 부분!
		}
		if(MAX < temp1) MAX = temp1;
		if(MAX < temp2) MAX = temp2;
		
		printf("#%d %d\n", test_case, MAX);
	}
	return 0;
}

추천) 1210. ladder1 문제를 먼저 풀기를 추천한다.

https://masso.tistory.com/23?category=881145

입력)

총 10개의 테스트 케이스

테스트 케이스의 번호, 사다리 정보가 들어있는 100 x 100 크기의 이차원 배열

(0: 아무것도 없음, 1 : 사다리, 2 : 도착 지점)

출력)

# 해당 테스트 케이스 번호, 가장 짧은 이동 거리를 가지는 사다리의 y index 출력

입, 출력 분석)

입력을 보면 마지막 줄에 존재해야할 2가 없음에 주의해야 한다.

핵심)

1210. ladder1 문제 풀이 링크 참고

입력 분석을 통해
- x == 99에 도달할 때까지, 가장 짧은 칸을 이동해온 y index를 구해야 함을 알았다.

복수 개인 경우 가장 큰 x좌표
- y(0 -> 99)로 탐색하며, 짧거나 같은 거리를 가지는 사다리가 있을 때 y index를 갱신하면 된다.

예시 분석)

(생략)

실수) 

- 도착 지점에 도착하는 사다리 중에 짧은 거리를 가지는 사다리를 구하는 문제인 줄 알았는데,가만히 입력을 보니까 2가 없는 것을 알게 되었다. (이래서 사람이 편견이 무섭다)

구현)

#include<iostream>
using namespace std;

int map[100][100]; // 100x100 크기의 이차원 배열
int dx[3] = { 1, 0, 0 };  // 0: 아래, 1: 왼쪽, 2: 오른쪽
int dy[3] = { 0, -1, 1 }; // 0: 아래, 1: 왼쪽, 2: 오른쪽

int main(int argc, char** argv) {
	int test_case, T = 0, ans = 0;
	for (test_case = 1; test_case <= 10; ++test_case) {
		scanf("%d", &T);
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++)
				scanf("%d", &map[i][j]);
		}
		int minLen = 10000; // 0. minLen 정의
		for (int j = 0; j < 100; j++) {
			if (!map[0][j]) continue;
			int x = 0, y = j, dir = 0, len = 1; // 1. len 정의
			while (x < 100) {
				int cnt = 0, key = 0;
				for (int i = 0; i < 3; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 0 || nx >= 100 || ny < 0 || ny >= 100) continue;
					if (map[nx][ny]) {
						cnt++;	key += i; // 아래 0, 왼 1, 오 2
					}
				}
				if (cnt == 2 && key < 3) { // 회전
					if (dir == 0) dir = key;
					else dir = 0;
				}
				if (x == 99) break;
				x += dx[dir]; y += dy[dir];	len++; // 2. 총 len 구하기
			}
			if(minLen >= len){ // 3. len 갱신하기
				minLen = len;
				ans = j;
			}
		}
		printf("#%d %d \n", T, ans);
	}
	return 0;
}

입력)

총 10개의 테스트 케이스

테스트 케이스의 번호, 사다리 정보가 들어있는 100 x 100 크기의 이차원 배열

(0: 아무것도 없음, 1 : 사다리, 2 : 도착 지점)

출력)

# 해당 테스트 케이스 번호, 지정된 도착점에 대응되는 사다리의 y index 출력

입, 출력 분석)

(생략)

핵심)

사다리를 그릴 때, 방향을 고려하여 그리는 것이 핵심이다.

한 칸씩 사다리를 타고 내려간다고 가정하고, 1의 여부를
자신의 아래,왼쪽,오른쪽 영역을 탐구한다고 가정했을 때,

회전하는 경우는
1) 1의 cnt가 2이고

2) 1인 영역이 (아래 또는 왼쪽), (아래 또는 오른쪽)을 가진다
    따라서 1인 영역을 발견했을 때 key를 두어,
    (아래 또는 왼쪽) : key = 0 + 1 -> 왼쪽

    (아래 또는 오른쪽) : key = 0 + 2 -> 오른쪽

    key < 3 일 때 회전한다.
    (key == 3일 때는 핑크색, cnt 가 2인 경우)

현재 어느 방향으로 오고 있었는지(dir) 확인하여, 회전하는 경우에 알맞게 방향을 바꾸면 된다.

예시 분석)

(생략)

실수) 

- 모든 경우의 수를 저렇게 따져보기 전에 복잡하고 내가 다루지 않았던 유형이라 기피했던 것 같다..
  (질질 끌다가 결국에 할 꺼면서...)

- 설계 초반에 핑크색 경우에서 cnt == 2 일 때를 cnt == 1로 잘못 계산했다.

- while(x<100)에서 x=99일 때 x+=dx[dir]; y+dy[dir]; 때문에 if(map[x][y] == 2)가 제대로 되지 않아서
  if(x==99) break; 문을 넣었다. (사실 map[x-1][y] == 2 해볼까 고민도 했다..ㅎ)

구현)

#include<iostream>
using namespace std;

int map[100][100]; // 100x100 크기의 이차원 배열
int dx[3] = { 1, 0, 0 };  // 0: 아래, 1: 왼쪽, 2: 오른쪽
int dy[3] = { 0, -1, 1 }; // 0: 아래, 1: 왼쪽, 2: 오른쪽

int main(int argc, char** argv) {
	int test_case, T = 0, ans = 0;
	for (test_case = 1; test_case <= 10; ++test_case) {
		scanf("%d", &T);
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++)
				scanf("%d", &map[i][j]);
		}
		for (int j = 0; j < 100; j++) {
			if (!map[0][j]) continue;
			int x = 0, y = j, dir = 0; ans = j;
			while (x < 100) {
				int cnt = 0, key = 0;
				for (int i = 0; i < 3; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 0 || nx >= 100 || ny < 0 || ny >= 100) continue;
					if (map[nx][ny]) {
						cnt++;	key += i; // 아래 0, 왼 1, 오 2
					}
				}
				if (cnt == 2 && key < 3) { // 회전
					if (dir == 0) dir = key;
					else dir = 0;
				}
				if (x == 99) break;
				x += dx[dir]; y += dy[dir];
			}
			if (map[x][y] == 2) {
				ans = j;	break;
			}
		}
		printf("#%d %d \n", T, ans);
	}
	return 0;
}

입력)

총 10개의 테스트케이스

1000개 이하의 빌딩의 높이가 주어진다.
이 빌딩의 높이는 최대 255이다.
맨 왼쪽 두 칸과 오른쪽 두 칸은 0이다. (건물이 지어지지 않기 때문)

출력)

#(테스트 케이스 번호) (해당 테케에서 조망권이 확보된 세대의 수)

입, 출력 분석)

(생략) int로 다루면 된다.

핵심)

해당 빌딩에서 조망권이 확보된 개수 = 해당 빌딩 높이 - 좌우 두 칸 사이에 제일 높은 빌딩의 높이

예시 분석)

index 2와 6을 통해 내 코드가 잘 구현이 되었는지 디버깅을 돌려보았다.

실수) 

- 좌우 두 칸 빌딩의 높이가 낮을 때만 조망권 개수를 계산하면 되는데,
  차이 구하는데 정신 팔려서  abs() 함수로 처리하고 있었다.

- 테스트 케이스 for문 안에서 갱신되어야 하는 변수를 밖에서 갱신해서,
   #1 691 #2 9092+691=>9783이 나왔다..
  (숫자보고 딱 어? 뭔가 밀렸다! 감잡아서 다행이지.. 시험장이었으면 멘탈 털렸을 것 같다..)

구현)

#include<stdio.h>
using namespace std;

int main(int argc, char** argv){
	int test_case = 1, cnt = 0;
	for (; test_case <= 10; ++test_case) {
		int heights[1000] = {0, }, total = 0;
		scanf("%d", &cnt);
		for (int i = 0; i < cnt; i++)
			scanf("%d", &heights[i]);
		for (int i = 2; i <= cnt-3; i++){
			int viewCnt = heights[i], temp = 0;

			for (int d = 1; d <= 2; d++){
				if(heights[i] <= heights[i+d] || heights[i] <= heights[i-d]){
					viewCnt = 0;	break;
				}				
				temp = heights[i] - heights[i + d];
				if(temp < viewCnt) viewCnt = temp;
				temp = heights[i] - heights[i - d];
				if (temp < viewCnt) viewCnt = temp;
			}
			total += viewCnt;
		}
		printf("#%d %d\n", test_case, total);
	}
	return 0;
}

입력)

1이상 100이하인 100개의 height이 주어진다.

덤프 횟수는 1이상 1000이하로 주어진다.

총 10개의 테스트 케이스가 주어지며,

[ 덤프 횟수 + 100개의 높이 ] 형식으로 들어온다.

출력)

#부호 최고점 - 처저점의 높이 차

입, 출력 분석)

width가 100이므로 배열의 크기도 100이다.

예시 분석)

(생략)

핵심)

최고점과 최저점을 빠르게 찾기 위해

height가 저장된 배열과 max값, min값의 index의 개념을 잘 알면 된다.

실수) 

printf인데 scanf 로 적어서 출력이 안 되는 황당한 실수를 했다.

구현)

#include<stdio.h>
using namespace std;

int main(int argc, char** argv) {
	int test_case;

	for (test_case = 1; test_case <= 10; ++test_case) {
		int heights[100] = {0,};
		int dump_cnt = 0, diff = 0;
		int maxIdx = 0, minIdx = 0; 
		scanf("%d", &dump_cnt);
		for (int w = 0; w < 100; w++){
			scanf("%d", &heights[w]);
			if(heights[maxIdx] < heights[w]) maxIdx = w;
			if(heights[minIdx] > heights[w]) minIdx = w;
		}
		
		for (int i = 0; i < dump_cnt; i++){
			--heights[maxIdx];
			++heights[minIdx];
			for (int w = 0; w < 100; w++) {
				if (heights[maxIdx] < heights[w]) maxIdx = w;
				if (heights[minIdx] > heights[w]) minIdx = w;
			}
		}
		diff = heights[maxIdx] - heights[minIdx];
		printf("#%d %d\n", test_case, diff);
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}