www.acmicpc.net/problem/14891

 

14891번: 톱니바퀴

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터

www.acmicpc.net

1. 풀이방법

- 구현문제입니다.. 그냥 문제에서 주는 조건에 맞춰 구현만하면 되는 듯 합니다.

 

- 톱니바퀴 개수도 정해져있고... 쉬운편인 것 같습니다.

 

- 저는 0,1,2,3 톱니바퀴에 대한 회전유무를 판단하는 벡터를 선언해서 돌아갈 지 말지를 체크해준 뒤

   돌렸습니다....!

 

 

 

2. 주의사항

- 처음에 연쇄적인 회전(?) 일까 라고 생각했는데 그건 아니고 4개가 한번에 빡 돌아가는 그런 것...

 

 

 

3. 나의코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

char topni[4][8];
int K;
int resultscore;

void inputs() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 8; j++) {
			cin >> topni[i][j];
		}
	}
}


void rotate(int index, int dir) { //0,1,2,3
	vector<pair<bool,int>> turn(4); //first= 회전할지 말지, second=방향

	for (int i = 0; i < 4; i++) { //초기화
		turn[i].first = false; turn[i].second = 0;
	}
	turn[index].first = true; turn[index].second = dir;
	//왼쪽확인
	char current=topni[index][6];
	int direction = dir;

	for (int i = index - 1; i >= 0; i--) {
		if (current != topni[i][2]) {
			turn[i].first = true; turn[i].second = (-1)*direction; //반대방향
			current = topni[i][6]; direction *= (-1);
		}
		else break; //이게 회전을 안한다면 그 옆은 볼필요 x
	}
	//오른쪽확인
	direction = dir;
	current = topni[index][2];
	for (int i = index + 1; i < 4; i++) {
		if(current!=topni[i][6]) {
			turn[i].first = true; turn[i].second = (-1)*direction;
			current = topni[i][2]; direction *= (-1);
		}
		else break; //이게 회전을 안한다면 그 옆은 볼필요 x
	}
	
	//회전
	for (int i = 0; i < 4; i++) {
		if (turn[i].first == true) { //회전한다면
			if (turn[i].second == 1) { //시계방향
		  		char tmp=topni[i][7];
				for (int j = 6; j >= 0; j--) topni[i][j + 1] = topni[i][j];
				topni[i][0] = tmp;
			}
			else { //반시계방향
				char tmp = topni[i][0];
				for (int j = 1; j <= 7; j++) topni[i][j - 1] = topni[i][j];
				topni[i][7] = tmp;
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cin.tie(0);
	inputs();
	cin >> K;
	int index, dir;
	for (int i = 0; i < K; i++) {
		cin >> index >> dir;
		rotate(index-1, dir);
	}
	if (topni[0][0] == '1') resultscore += 1;

	if (topni[1][0] == '1') resultscore += 2;

	if (topni[2][0] == '1') resultscore += 4;

	if (topni[3][0] == '1') resultscore += 8;

	cout << resultscore << "\n";

	return 0;
}

'알고리즘 문제풀이 > 구현' 카테고리의 다른 글

백준 14499 [C++]  (0) 2020.12.08
백준 14503 [C++]  (0) 2020.12.08
백준 2840 [C++]  (0) 2020.12.06
백준 2033 C++  (0) 2020.11.25
백준 14890 [C++]  (0) 2020.10.21

www.acmicpc.net/problem/2840

 

2840번: 행운의 바퀴

첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓

www.acmicpc.net

1. 풀이방법 

- 구현자체는 어렵지 않습니다..

 

- 배열은 ?로 초기화 해주고

 

- 조건에 따라 INDEX를 취향 껏 조절하시면 됩니다. (방향에 맞춰)

 

 

 

2. 주의사항

- 많이 틀린 이유......예외사항이 중요합니다....

 

- (1) 같은 문자가 바퀴에 중복으로 붙여져서는 안된다.

 

- (2) 한 자리에 여러개의 문자가 붙여질 수는 없다.

 

- 이 떄는 !를 출력해야합니다.

 

- !!!!! 단, 입력은 돌리면서 상황을 보여주는 것이기 때문에 돌렸을 때 상황이 같은 자리를 가리킬 수도 있기 때문에

 

- 입력으로 같은 문자가 두번이 들어와도 그것이 같은자리를 가리키고 있는 경우에는 허용이 됩니다...!!

 

- 이를 조건문에 추가로 걸어주어야 합니다 !

 

- 너무 쉽다생각했다가 예외처리에서 애좀 먹은 문제입니다...ㅠ

 

 

 

3. 나의코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int N, K;
void setpan(vector<char> &pan) {
	for (int i = 0; i < N; i++) {
		pan[i] = '?';
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	vector<char> pan(N);
	setpan(pan);
	int index;
	for (int i = 0; i < K; i++) {
		int count; char tmpc;
		cin >> count >> tmpc;
		if (i == 0) { pan[0] = tmpc; index = 0; continue; }
		index = (count + index) % N;
		//돌렸을 때 같은문자(같은 자리)는 나올 수 있다. 그것마저 아니면 틀린 원판
		if (pan[index] != '?'&& pan[index] != tmpc) { cout << "!"; return 0; }
		else {
			pan[index] = tmpc;
		}
	}
	//중복체크
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if(pan[i]!='?' &&pan[i]==pan[j]) { cout << "!"; return 0; }
		}
	}
	for (int i = 0; i < N; i++) {
		cout << pan[index];
		index--;
		if (index == -1) index = N - 1;
	}
	return 0;
}

'알고리즘 문제풀이 > 구현' 카테고리의 다른 글

백준 14503 [C++]  (0) 2020.12.08
백준 14891 [C++]  (0) 2020.12.06
백준 2033 C++  (0) 2020.11.25
백준 14890 [C++]  (0) 2020.10.21
백준 17406 [C++]  (0) 2020.10.18

 

www.acmicpc.net/problem/2033

 

2033번: 반올림

정수 N이 주어져 있을 때 이 수가 10보다 크면 일의 자리에서 반올림을 하고, 이 결과가 100보다 크면 다시 10의 자리에서 반올림을 하고, 또 이 수가 1000보다 크면 100의 자리에서 반올림을 하고.. (

www.acmicpc.net

1. 풀이 방법

- 문제를 잘 읽고 뒷자리 수부터 차례대로 반올림을 실행하시면 됩니다.

 

2. 주의 사항

- 문제를 잘읽읍시다. (전.. 제대로 안읽어서 제일 앞자리 다음 수 (두번쨰자리수) 에서만 반올림 하게 짰다가 그게 아니더라구요);; 귀찮;; 

 

3. 나의 소스

#include<iostream>
using namespace std;

int N;
int initnum=10;
int tmp;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>N;
    while(N/initnum!=0){
        if(N%initnum>=5*(initnum/10)){
                N+=initnum*1;
                tmp=(N%initnum)/(initnum/10);
                N-=(tmp*(initnum/10));
        }
        else {
            tmp=(N%initnum)/(initnum/10);
            N-=(tmp*(initnum/10));
            }
        initnum*=10;
    }
    cout<<N<<"\n";
    return 0;
}

 

'알고리즘 문제풀이 > 구현' 카테고리의 다른 글

백준 14891 [C++]  (0) 2020.12.06
백준 2840 [C++]  (0) 2020.12.06
백준 14890 [C++]  (0) 2020.10.21
백준 17406 [C++]  (0) 2020.10.18
백준 15686 [C++]  (0) 2020.10.17

www.acmicpc.net/problem/17135

 

17135번: 캐슬 디펜스

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

www.acmicpc.net

 

 

1.풀이방법

 

 

- 3명의 궁수가 (N,0) (N,M-1)까지 배치될 수 있는 모든 CASE를 생성하여 게임을 시작합니다. (조합)

 

 

- 격자에서 모든 적이 사라지면 게임을 종료

 

 

- 3명의 궁수를 대상으로 모든 적들의 거리를  계산후 좌표와 거리를 구조체로 선언하여, eset(enemy set)에 넣고

 

 

- sort를 진행(거리가 가까운 순, 같으면 좌표 y가 더 작은 순(왼쪽))

 

 

 

 

 

2. 주의사항

 

 

- 조합만 잘 구현하면 문제는 조건대로 찬찬히 구현하면 해결 완료.

 

 

 

 

 

3.나의코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int ground[17][17];
int copyground[17][17];
bool selected[17];
vector<pair<int, int>> archer;
int maxresult = -1;
int N, M;
int D;
int enemycount;
struct enemy { int x; int y; int d; };

bool cmp(enemy a, enemy b) {
	if (a.d < b.d) { return true; }
	else {
		if (a.d == b.d) {
			if (a.y < b.y) { return true; }
			else { return false; }
		}
		return false;
	}
}

void inputs() {
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> ground[i][j];
			copyground[i][j] = ground[i][j];
		}
	}
}
void groundinit() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			ground[i][j] = copyground[i][j];
		}
	}
}
bool checkground() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (ground[i][j] == 1) { return false; }
		}
	}
	return true;
}
int abs(int n1, int n2) {
	if (n1 > n2) { return n1 - n2; }
	else return n2 - n1;
}
int getdistance(int x, int y, int x2, int y2) {
	return (abs(x, x2) + abs(y, y2));
};
void enemymove() {
	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; j < M; j++) {
			if (ground[i][j] == 1) {
				ground[i + 1][j] = 1; ground[i][j] = 0;
			}
		}
	}
}
void startgame() {
	while (1) {// 반복한번 = 1턴
		if (checkground() == true) { 
			if (maxresult < enemycount) { maxresult = enemycount; }
			return;
		}
		vector<enemy> eset[3];
		for (int i = 0; i < archer.size(); i++) {
			for (int a = 0; a < N; a++) {
				for (int b = 0; b < M; b++) {
					if (ground[a][b] == 1) {
						if (getdistance(archer[i].first, archer[i].second, a, b) <= D) {
							enemy tmp; tmp.x = a; tmp.y = b; tmp.d = getdistance(archer[i].first, archer[i].second, a, b);
							eset[i].push_back(tmp); //1명의 궁수당 적이 들어있음 거리와 함께
						}
					}
				}
			}
			sort(eset[i].begin(), eset[i].end(), cmp);
		}
		//각각의 궁수에 대해서 0번쨰 인덱스의 적이 죽을 차례
		for (int i = 0; i < archer.size(); i++) {
			if (eset[i].empty() == true) continue; //사정거리내의 적이 없음
			if (ground[eset[i][0].x][eset[i][0].y] == 1) {
				ground[eset[i][0].x][eset[i][0].y] = 0; //적을 없앤다
				enemycount++;
			}
		}
		enemymove();
	}
}


void makecase(int index,int num) {
	if (num == 3) {
		enemycount = 0;
		groundinit();
		startgame(); return;
	}
	pair<int, int> tmp;
	tmp.first = N;
	for (int i = index; i < M; i++) {
		if (selected[i] == true  ) continue;
		tmp.second = i;
		archer.push_back(tmp);
		selected[i] = true;
		makecase(i,num + 1);
		archer.pop_back();
		selected[i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	inputs();
	makecase(0,0);
	cout << maxresult;

	return 0;
}

'알고리즘 문제풀이 > 완탐' 카테고리의 다른 글

백준 1107 [C++]  (0) 2020.12.14
백준 14500 [C++]  (0) 2020.12.05
백준 17136 [C++]  (0) 2020.10.20
백준 16637 [C++]  (0) 2020.10.19
백준 17070 [C++]  (0) 2020.10.14

www.acmicpc.net/problem/14890

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

1. 풀이방법.

 

- 말 그대로 그냥 문제 조건을 구현해야 하는데...

 

 

- 처음엔 왼쪽으로 쭉한번보고 오른쪽으로 쭉한번보고 위아래도 마찬가지로 하면된다 생각했었는데

 

 

- 223322 [L=2] 같은 경우가 안되는 것을 보고 접근 방식을 바꿨습니다.

 

 

-높이가 1차이 나는 친구를 만날경우 나보다 큰 친구면 나부터 뒤쪽을 보고

 

 

- 나보다 작은 친구면 나의 앞쪽부터 L만큼을 살펴 보았습니다.

 

 

 

 

 

 

2. 주의사항

 

- 나보다 큰 친구, 작은친구 의 분류로 나눠서 확인할 때, 저는 현재 위치를 INIT 앞쪽 친구를 loadmap[i][j]로 두었기 때문

 

 

- 에 비교문에서 값에 신경을 써야했습니다.

 

 

- 문제에 다양한 예시입력이 있어서 다행이었습니다.....아니였으면 꽤 오래 답을 찾아야 했을 것 같습니다.

 

 

- 후....문제에 대한 아이디어가 생각나면 그 아이디어로 해결이 될 것만 같은 [즉, 예외되는 사항이 발생하는 경우 를 잘

 

 

-떠올리지 못하는 것 같습니다]

 

 

- 코드를 작성하기 전에 한번 더 생각해보고 천천히 접근하자.....!

 

 

 

 

3. 나의코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int N;
int loadmap[101][101];
int L;
int result = 0;
int init;
bool check;
bool checkrow[101];

void inputs() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> loadmap[i][j];
		}
	}
}
int gap(int a, int b) {
	if (a > b) return a - b;
	else { return b - a; }
}
void initcheck() {
	for (int i = 0; i < 101; i++) {
		checkrow[i] = 0;
	}
}
void lookr() {
	for (int i = 0; i < N; i++) {
		initcheck();
		init = loadmap[i][0];
		check = true;
		for (int j = 1; j < N; j++) {
			if (init == loadmap[i][j]) { init = loadmap[i][j]; continue; }
			if (gap(init, loadmap[i][j]) == 1) { //높이1차이
				if (init < loadmap[i][j]) { //벽을 만남(나보다 큰)
					if (j - L < 0) { check = false; break; }
					else {
						for (int k = 1; k <= L; k++) {
							if(checkrow[j-k]==true || loadmap[i][j - k] != init)
							 { check = false; break; }
						}
						for (int k = 1; k <= L; k++) {
							checkrow[j - k] = true;
						}
						if (check == false) break;
					}
				}
				else { //나보다 작은 친구를 만남
					if(j+L>N) { check = false; break; }
					else{
						for (int k = 0; k < L; k++) {
							if (checkrow[j+k]==true||loadmap[i][j + k] != init-1)
							{ check = false; break; }
						}
						for (int k = 0; k < L; k++) {
							checkrow[j + k] = true;
						}
						if (check == false) break;
						j += L-1; //앞에다가 경사로를 놓았을 경우 점프가 필요
					}
				}
			}
			else {check = false; break;} //높이1차이 이상
		init = loadmap[i][j];
		}
		if (check == true) { result++;  }
	}
}
void looku() {
	for (int i = 0; i < N; i++) {
		initcheck();
		init = loadmap[0][i];
		check = true;
		for (int j = 1; j < N; j++) {
			if (init == loadmap[j][i]) { init = loadmap[j][i]; continue; }
			if (gap(init, loadmap[j][i]) == 1) { //높이1차이
				if (init < loadmap[j][i]) { //벽을 만남(나보다 큰)
					if (j - L < 0) { check = false; break; }
					else {
						for (int k = 1; k <= L; k++) {
							if (checkrow[j - k] == true || loadmap[j - k][i] != init)
							{
								check = false; break;
							}
						}
						for (int k = 1; k <= L; k++) {
							checkrow[j - k] = true;
						}
						if (check == false) break;
					}
				}
				else { //나보다 작은 친구를 만남
					if (j + L > N) { check = false; break; }
					else {
						for (int k = 0; k < L; k++) {
							if (checkrow[j + k] == true || loadmap[j + k][i] != init - 1)
							{
								check = false; break;
							}
						}
						for (int k = 0; k < L; k++) {
							checkrow[j + k] = true;
						}
						if (check == false) break;
						j += L-1; //앞에다가 경사로를 놓았을 경우 점프가 필요
					}
				}
			}
			else { check = false; break; } //높이1차이 이상
			init = loadmap[j][i];
		}
		if (check == true) { result++;  }
	}
}

void checkingload() {
	lookr();
	looku();
	cout << result;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> L;
	inputs();
	checkingload();
	return 0;
}

'알고리즘 문제풀이 > 구현' 카테고리의 다른 글

백준 2840 [C++]  (0) 2020.12.06
백준 2033 C++  (0) 2020.11.25
백준 17406 [C++]  (0) 2020.10.18
백준 15686 [C++]  (0) 2020.10.17
백준 3190 [C++]  (0) 2020.10.17

www.acmicpc.net/problem/17406

 

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의

www.acmicpc.net

 

 

1. 풀이 방법

 

- 경우의 수는 명령의 순서에 따라 결과가 달라지므로 순열로 구했습니다.

 

 

- 회전을 구현해야 하는데, 바깥쪽 부터 한 겹씩 회전을 시키는 순으로 했고

=

  맨 안쪽에 남은 하나는 오른쪽으로 가려고 하는데 이미 방문한 곳이면 break 하게끔 하였습니다.

 

 

-코드가 많이 길어졌네요...ㅠ

 

 

 

 

2.주의할 점.

 

- 코드가 길어지다보니 처음 짠 부분에서 이곳 저곳에서 문제가 발생...

   디버깅을 한참했습니다...

 

 

-디버깅을 아예 안하기는 쉽지 않겠지만 처음 짤 때 그래도 좀 세심하게 해야겠네요...

 

 

-그리고 (r-s,r+s) 입력이 이런식 이기때문에 행과 열의 수는 모두 홀수 입니다.

(처음에 짝수 개도 되는 경우의 수도 생각하고 짰었는데...풀다보니 발견...)

 

 

- 조건에 따른 문제를 정확하게 파악해야겠습니다...

 

 

 

 

3. 나의코드

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N, M;
int K,r,s;
int doublearr[51][51]; //본 2차원 배멸 (변화 x)
int caculdoublearr[51][51]; //case별 결과값을 뽑아내기 위한 배열
int copydoublearr[51][51]; //이동을 위해 값을 복사해놓을 임시배열
bool check[51][51];
bool selected[7];
vector<int> resultmin;

struct rcs {
	int r,c,s;
};
vector<rcs> command; //입력받은명령
vector<rcs> casecommand; // 각 경우의수 (시뮬레이션 돌릴)

void input() { // 입력받는 함수		
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> doublearr[i][j];
		}
	}
	rcs tmp;
	for (int i = 0; i < K; i++) {
		cin >> tmp.r >> tmp.c >> tmp.s;
		command.push_back(tmp);
	}
}
void copyarr() { // 원본배열은 그대로 두고 복사해서 사용 (각 테스트케이스마다 써야하므로)
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			copydoublearr[i][j] = doublearr[i][j];
			caculdoublearr[i][j] = doublearr[i][j];
		}
	}
}
void initcheck() { // 방문배열 초기화
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			check[i][j] = false;
		}
	}
}
void copycal() { //한번회전한 배열을 계산을 위한 배열에 복사
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			copydoublearr[i][j] = caculdoublearr[i][j];
		}
	}
}
void turnarr(int r, int c, int s) { //회전을 구현
	int x = r - s;
	int y = c - s;
	int tmpcount = 0;
	int totalcount = 8 * s; //연산해야하는 횟수 한 바퀴에
	char dir = 'R';
	initcheck();
	while (1) {
		if (totalcount == tmpcount) { //바깥한바퀴 -> 안쪽 바퀴로 들어감
			x += 1; y += 1; s -= 1; totalcount = 8 * s;
			tmpcount = 0;
		}
		if (dir == 'R') {
			if (check[x][y+1] == true) { copycal(); break;
			}
			caculdoublearr[x][y + 1] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			y += 1;
			if (y == c + s) { dir = 'D'; }
		}
		else if (dir == 'D') {
			caculdoublearr[x + 1][y] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			x += 1;
			if (x == r + s) { dir = 'L'; }
		}
		else if (dir == 'L') {
			caculdoublearr[x][y - 1] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			y -= 1;
			if (y == c - s) { dir = 'U'; }
		}
		else {
			caculdoublearr[x - 1][y] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			x -= 1;
			if (x == r - s) { dir = 'R'; }
		}
	}
}
int getmin() { //배열의 최소값을 뽑아내는 함수
	int mini = 5001;
	for (int i = 1; i <= N; i++) {
		int tmpsum = 0;
		for (int j = 1; j <= M; j++) {
			tmpsum += caculdoublearr[i][j];
		}
		if (tmpsum < mini) { mini = tmpsum; }
	}
	return mini;
}
void relocating() { //명령을 수행 (회전명령)
	copyarr();
	for (int i = 0; i < K; i++) {
		turnarr(casecommand[i].r, casecommand[i].c, casecommand[i].s);
	}
	resultmin.push_back(getmin());
}
void simulation(int n) { //순열 경우의 수 생성
	if (n == K) {
		relocating(); 
		return;
	}
	for (int i = 0; i < command.size(); i++) {
		if (selected[i] == true) continue;
		selected[i] = true;
		casecommand.push_back(command[i]);
		simulation(n+1);
		casecommand.pop_back();
		selected[i] = false;
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	input();
	simulation(0);
	sort(resultmin.begin(), resultmin.end());
	cout << resultmin[0];
	return 0;
}

'알고리즘 문제풀이 > 구현' 카테고리의 다른 글

백준 2033 C++  (0) 2020.11.25
백준 14890 [C++]  (0) 2020.10.21
백준 15686 [C++]  (0) 2020.10.17
백준 3190 [C++]  (0) 2020.10.17
백준 18406 [C++]  (0) 2020.10.16

www.acmicpc.net/problem/3190

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

1. 풀이방법

 

- 문제의 그대로를 구현하면 되는 문제인데.. 아마 20대 중후반 분들은 한번쯤은 해보시지 않았을까....

 

- 저의 방법은 머리와 꼬리의 현재좌표를 계속 갱신하는 것인데...

 

- 핵심은 머리가 지나가면서 자신이 어디로 지나갔었는지를 지도에 기록을 해놓아야 하는 것.

 

- 사과가 없어서 꼬리가 짧아 져야 할 경우 지도에 기록해둔 머리가 갔던 방향(꼬리 좌표에서)을 확인하고 그 방향으로       이동합니다.. (directionjirung[][])

 

- 방향전환 명령어는 큐를 이용해서 pair의 first(시간) 이 게임시간과 일치할 때 pop을 하여 썼습니다.

 

 

 

2. 주의할 점

 

- 하.....전 꽤 오래 걸렸는데....아이디어를 생각하고 구현한게 어려운게 아니라...

 

- 변수를 수정할때 조심해야할 것...

tailx+=directionjirung[tailx][taily]; //이 따구로 하면 변경된 tailx가

taily+=directionjirung[tailx][taily]; //여기에 반영되기 때문에 매우 엉망인 값이 나옵니다..

 

- <변경된 코드는 이렇습니다>

int tmpx=tailx;

int tmpy=taily;

tailx+=directionjirung[tmpx][tmpy];

taily+=directionjirung[tmpx][tmpy];

 

기본적인 실수를 하고도 못찾아서 한참을 찾았네요.....지도도 출력하고...;;

 

이제부터 더 주의해서 세심하게 코드를 짜야겠습니다

 

감을 다시 잡아야겠네요....

 

 

3. 나의코드

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int map[101][101]; //사과가 있는지 여부를 알기 위해
int jirung[101][101];//지렁이의 현재위치
int directionjirung[101][101]; //꼬리를 위한 지렁이가 그 좌표에서 보고있던 방향을 기록
int N;
int K;
int dx[4] = {0,1,0,-1}; //동남서북
int dy[4] = {1,0,-1,0};
int direction=0; //지렁이가 보고있는 방향(처음엔 동쪽 보고있다.)
int gamesecond;
int L;
int headx, heady,tailx,taily;
queue<pair<int, char>> dq;

void setapple() {
	int x, y;
	for (int i = 0; i < K; i++) {
		cin >> x >> y;
		map[x][y] = 1; //사과가 존재하는 위치
	}
}
void setqueue() {
	pair<int, char> tmppair;
	for (int i = 0; i < L; i++) {
		cin >> tmppair.first >> tmppair.second;
		dq.push(tmppair);
	}
}

int main() {
	cin >> N >> K;
	setapple();
	cin >> L;
	setqueue();
	headx = 1; heady = 1; tailx = 1; taily = 1;
	jirung[1][1] = 1;
	while (1) {
		while (1) {
			if (dq.empty() == false && gamesecond == dq.front().first) {
				if (dq.front().second == 'L') { //왼쪽 회전
					direction = (direction + 3) % 4;
				}
				else {//오른쪽 회전
					direction = (direction + 1) % 4;
				}
				dq.pop();
			}
			else break;
		}
		gamesecond++;

		directionjirung[headx][heady] = direction; //꼬리를위해 방향을 기록먼저 !
		headx += dx[direction]; heady += dy[direction];
		if (headx <= 0 || heady <= 0 || headx > N || heady > N || jirung[headx][heady] == 1) {  break; } //종료조건 (map의 범위 1~N)

		jirung[headx][heady] = 1; //머리가 도착한 곳 표시
		if (map[headx][heady] == 1) { //사과가 있다면
			map[headx][heady] = 0; 
		}
		else {
			jirung[tailx][taily] = 0; //사과가 없다면 꼬리좌표 지워짐
			int tmptailx = tailx;
			int tmptaily = taily;
			tailx = tailx + dx[directionjirung[tmptailx][tmptaily]]; //꼬리의 위치 업데이트 (머리가 지나갈때 간 방향으로 업데이트)
			taily = taily + dy[directionjirung[tmptailx][tmptaily]];
		}
	}
	cout << gamesecond << "\n";
			return 0;
}

'알고리즘 문제풀이 > 구현' 카테고리의 다른 글

백준 2033 C++  (0) 2020.11.25
백준 14890 [C++]  (0) 2020.10.21
백준 17406 [C++]  (0) 2020.10.18
백준 15686 [C++]  (0) 2020.10.17
백준 18406 [C++]  (0) 2020.10.16

www.acmicpc.net/problem/18406

 

18406번: 럭키 스트레이트

첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다.

www.acmicpc.net

1.풀이방법

 

- string으로 입력을 받아와서 index하나씩 보면서 '0'은 아스키 코드 상 48이므로 직접 숫자로 변환하여

  합을 구해서 비교해주었습니다.

 

- 문제 자체에 예외사항들이 거의다 이미 조건으로 배제 되어 따로 처리할 것도 없습니다.

 

 

 

2.주의점.

 

 

3.나의코드

 

#include<iostream>
#include<string>
using namespace std;

int main() {

	string inputs;
	cin >> inputs;  //48 --> '0' (ASCII)
	int size = inputs.length()/2; //half
	int leftsum = 0;
	int rightsum = 0;
	for (int i = 0; i < size; i++) {
		leftsum += inputs[i] - 48;
		rightsum += inputs[i + size] - 48;
	}
	if (leftsum == rightsum) cout << "LUCKY";
	else cout<<"READY";

	return 0;
}

'알고리즘 문제풀이 > 구현' 카테고리의 다른 글

백준 2033 C++  (0) 2020.11.25
백준 14890 [C++]  (0) 2020.10.21
백준 17406 [C++]  (0) 2020.10.18
백준 15686 [C++]  (0) 2020.10.17
백준 3190 [C++]  (0) 2020.10.17

+ Recent posts