대엉코딩

www.acmicpc.net/problem/20056

1. 풀이방법

- 구현 문제이고 문제풀이에 필요한 알고리즘은 딱히 없습니다.

- 조건을 파악한뒤 이제 파이어볼이 이동할수 있는 지도가 연결되어 있다는 것이 중요한 것 같습니다.

- N을 넘어가면 다시 1로 오는 것이죠.

- 방향은 친절하게도 지도모양으로 줘서 8방향탐색 dx,dy를 설정해주시면 되고,

- 저같은 경우 파이어볼들을 저장하는 벡터 하나와 각 단계에서 ground[51][51]을 벡터로 선언해서,

- x,y에 이동한 파이어 볼이 있을경우 push_back으로 각 좌표에 매달아주는 느낌으로 구현하였습니다.

- 그렇게 파이어볼이 모두 이동시킨뒤 ground(맵)을 보면서 파이어볼이 없는 좌표는 continue

- 한개있는 좌표는 그대로 다시 totalfireball에 push, 두개 이상인 것은 문제 조건에 맞춰 재조정한후

- 4개의 파이어볼을 다시 totalfireball에 push 해주었습니다.

- 각 단계에서 vector들 clear()를 해주었구요.

2. 주의사항

- 이게 s(속력)이 최대 1000이 될수도 있습니다.

- 그래서 단순히 0보다 작아지면 N을 더해주거나 N보다 커지면 0으로 만들거나 하려면 이 자체도 반복문 처리를 해주어

- 합니다 그래서 그냥 아래와 같이 처리하였습니다.

- int newx = ((totalfireball[i].x) + dx[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;
  int newy = ((totalfireball[i].y) + dy[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;

- 250*N을 더해준 이유는 % 모듈러 연산을 할 때 음수가 나오는 것을 방지하기 위함인데

- N의 최솟값은 4이고 s의 최대값은 1000이므로 250*N은 1000보다 같거나 크면서 N 모듈러 연산에는 영향을 끼치지 

- 않는 수로 설정하였습니다(N의배수 이므로)

3. 나의코드

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

int N, M, K;
int dx[8] = { -1,-1,0,1,1,1,0,-1 };//8방향탐색
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };

struct fireball {
	int x,y,m, s, d;
};
vector<fireball> ground[51][51];
vector<fireball> totalfireball;
void inputs() {
	cin >> N >> M >> K;
	int tx, ty, tm, ts, td;
	for(int i=0;i<M;i++){
		cin >> tx >> ty>>tm>>ts>>td;
		totalfireball.push_back({ tx-1,ty-1,tm,ts,td }); // 난 0~N-1
	}
}
void groundclear() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ground[i][j].clear();
		}
	}
}
void moveball() {
	for (int i = 0; i < totalfireball.size(); i++) {
		int newx = ((totalfireball[i].x) + dx[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;
		int newy = ((totalfireball[i].y) + dy[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;
		ground[newx][newy].push_back({ newx,newy,totalfireball[i].m,totalfireball[i].s,totalfireball[i].d });
	}
}
void makenewball() {
	for(int i=0;i<N;i++){
		for (int j = 0; j < N; j++) {
			if (ground[i][j].empty()) continue; //비어있으면.
			else if (ground[i][j].size() == 1) { //파이어볼이 한개
				totalfireball.push_back(ground[i][j][0]);
			}
			else { //두개 이상인 경우
				int newm = 0; int news = 0;
				for (int k = 0; k < ground[i][j].size(); k++) {
					newm += ground[i][j][k].m;
					news += ground[i][j][k].s;
				}
				newm = newm / 5;
				if (newm == 0) continue;
				news = news / ground[i][j].size();


				bool check = false;
				for (int k = 0; k < ground[i][j].size(); k++) { //모두 홀수?
					if (ground[i][j][k].d % 2 == 0) { check = true; break; }
				}
				if (check == false) {
					totalfireball.push_back({ i,j,newm,news,0 });

					totalfireball.push_back({ i,j,newm,news,2 });

					totalfireball.push_back({ i,j,newm,news,4 });

					totalfireball.push_back({ i,j,newm,news,6 });
				continue;
				}

				check = false;
				for (int k = 0; k < ground[i][j].size(); k++) { //모두 짝수?
					if (ground[i][j][k].d % 2 == 1) { check = true; break; }
				}
				if (check == false) {
					totalfireball.push_back({ i,j,newm,news,0 });

					totalfireball.push_back({ i,j,newm,news,2 });

					totalfireball.push_back({ i,j,newm,news,4 });

					totalfireball.push_back({ i,j,newm,news,6 });
					continue;
				}
				// 둘다 아닐경우
				totalfireball.push_back({ i,j,newm,news,1 });

				totalfireball.push_back({ i,j,newm,news,3 });

				totalfireball.push_back({ i,j,newm,news,5 });

				totalfireball.push_back({ i,j,newm,news,7 });
			}
		}
	}
}
long long getm() {
	long long resultm = 0;
	for (int i = 0; i < totalfireball.size(); i++) {
		resultm += totalfireball[i].m;
	}
	return resultm;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	while (K--) {
		groundclear();
		moveball();
		totalfireball.clear();
		makenewball();
	}
	cout << getm() << "\n";


	return 0;
}

www.acmicpc.net/problem/20055

1. 풀이방법

- 그냥 조건대로만 구현해 주시면 됩니다.

- 컨베이어 벨트는 문제그대로 N의 최대값인 200을 채우고 INDEX를 그대로 쓰려고 201로 선언해주었고

- bool 타입의 로봇배열을 그의 절반만 선언해서 벨트의 index와 같이 맞추어 위치를 index로 접근하였습니다.

2. 주의사항

- 굳이 이 문제를 블로그에 남기는 데에는 문제설명자체가 얼핏 잘못이해하기 쉬워서입니다.

- 일단 일반적인 우리의 생각으로는 당연히 컨베이어벨트가 한칸움직이면 위의 물건도 따라 움직입니다.

- 그리고 이문제에서는 그와 별개로 로봇도 움직일 수 있다. 라는 것이 이 문제입니다.

- 결국 일반적인 컨베이어벨트의 이동 + 로봇의 이동이 모두 들어간 문제입니다.

- 처음에는 문제의 조건을 읽고 일반적인 컨베이어벨트의 이동에 대한 설명은 없어서 그것을 제외하고 해야하나??

- 벨트는 벨트대로 움직이고 나서, 로봇의 이동을 하는 것인가 생각하였지만 그것은 아니였습니다.

- 물론 테스트케이스가 여러개라서 그것들을 통해서 위의 의문을 걸러낼 수 있습니다.

3. 나의코드

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

int N, K;
int zerocount;
int p = 0;
int barr[201];
bool robo[101];

void ratate() { //barr[0]는 그냥 tmp용으로 사용
	barr[0] = barr[2 * N];
	for (int i = 2 * N; i >= 2; i--) { //벨트이동
		barr[i] = barr[i - 1];
	}
	for (int i = N - 1; i >= 1; i--) { //로봇이동
		robo[i + 1] = robo[i];
	}
	robo[1] = false;
	barr[1] = barr[0];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= 2*N; i++) {
		cin >> barr[i];
		if (barr[i] == 0) zerocount++;
	}
	while (1) {
		if (zerocount >= K) break;
		p++;
		ratate();
		if (robo[N] == true) { //내려오는 칸
			robo[N]= false;
		}
		for (int i = N - 1;  i >= 1; i--) { //이동관련
			if (robo[i] == true) {
				if (robo[i + 1] == false && barr[i + 1] >= 1) {
					robo[i] = false; robo[i + 1] = true;
					barr[i + 1]--;
					if (barr[i + 1] == 0) zerocount++;
				}
			}
		}
		if (robo[1] == false && barr[1] >= 1) { //올라가는 칸
			robo[1] = true; barr[1]--;
			if (barr[1] == 0) zerocount++;
		}
	}
	cout << p << "\n";
	return 0;
}

www.acmicpc.net/problem/1697

1. 풀이방법.

- 0<N==K<100000 이 되는 모든 경우의 수를 탐색해야합니다.

- 움직일 수 있는 경우의 수는 3가지 X+1,X-1,2*N

- DFS로 모든 경우의수를 탐색할경우 +1,-1씩 이동하는경우 때문에 스택오버플로우가 발생할 것 이라 판단했습니다.

- 그래서 큐를 이용하여 BFS로 해결하였습니다. 

- 딱히 다른 조건도 없어 기본적인 문제였습니다.

2. 주의사항

- 문제 조건 해석 및 판단.

3.나의코드

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

int N, K;
int resultsecond;
bool visit[100001]; //방문체크
queue<int> tmpq;


void bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			int thisvalue = tmpq.front();
			tmpq.pop();

			if (thisvalue == K) { //종료조건
				cout << resultsecond << "\n";  return;
			}

			if (thisvalue - 1 >= 0 && visit[thisvalue-1] == false) {
				visit[thisvalue - 1] = true;
				tmpq.push(thisvalue - 1);
			}
			if (thisvalue + 1 <= 100000 && visit[thisvalue+1] == false) {
				visit[thisvalue + 1] = true;
				tmpq.push(thisvalue + 1);
			}
			if (2 * thisvalue <= 100000 && visit[2*thisvalue] == false) {
				visit[2 * thisvalue] = true;
				tmpq.push(2 * thisvalue);
			}
		}
		resultsecond++;
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	tmpq.push(N);
	visit[N] = true;
	bfs();

	return 0;
}

www.acmicpc.net/problem/16397

1. 풀이방법

- 처음에는 재귀를 이용한 DFS로 모든 경우를 탐색하려고 생각하고 코드를 구상했으나,

- 문제 조건을 보시면 T가 최대 99,999이고, A버튼만 누를 경우 숫자가 1씩 증가하는데 N이 0일경우를 생각해보면

- 재귀를 이용해서 짰을때 stackoverflow를 만났습니다. (조건을 보고 미리 생각했어야되는데....으휴 덤벙덤벙)

- 원리는 비슷한데 queue를 이용해서 bfs로 똑같이 옮겨서 해결했습니다.

2. 주의사항

- 조건도 꼼꼼히 파악하자.

3. 나의코드

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

int N, T, G;
bool visit[100000];
queue<pair<int,int>> tmpq;



int getmodnum(int tmp) {
	int maxmod = 1;
	while (1) {
		if (tmp == 0) break;
		tmp /= 10;
		maxmod *= 10;
	}
	maxmod /= 10;
	return maxmod;
}

int bfs() {
	while (!tmpq.empty()) {
		int tmpn = tmpq.front().first;
		int tmpcnt = tmpq.front().second;
		tmpq.pop();
		if (tmpcnt > T) break;
		if (tmpn == G) return tmpcnt;

		int num = tmpn + 1;
		if (num < 100000 && visit[num] == false) {
			visit[num] = true;
			tmpq.push({ num,tmpcnt + 1 });
		}

		num = tmpn * 2;
		if (num < 100000) {
			int minusnum = getmodnum(num);
			num -= minusnum;
			if (num < 100000 && visit[num] == false) {
				visit[num] = true;
				tmpq.push({ num,tmpcnt + 1 });
			}
		}
	}
	return -1;
}

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

	cin >> N >> T >> G;
	tmpq.push({N, 0}); //시작점
	visit[N] = true;
	int result = bfs();
	if (result == -1) cout << "ANG" << "\n";
	else cout << result << "\n";
	return 0;
}

www.acmicpc.net/problem/1107

1. 풀이방법

- 개인적으로 참 어려웠던 문제였습니다...

- 처음에는 경우의 수를 나눠서 1번 (+,-만으로만 접근) 2번 (버튼만으로 접근이 가능한 경우) 3번 (버튼으로 근접하게 간 후 +,- 로 이동해야하는 경우) 3가지 중 min 값을 출력하자 라고 했습니다.

- 하지만 저 3번....! 저걸 찾아내는게 굉장히 까다로웠습니다. 숫자를 하나씩 맞춰본다거나, 

  고장난 버튼이면 최대한 근접한 버튼을 누르는데 위,아래 어느 숫자쪽으로 탐색을 해야하나....

- 하나의 아이디어를 준 것은 바로 +,-는 마지막에 눌러진다는 것입니다. +,- 버튼을 누르고 나서 숫자를 누를경우 

  처음 부터 다시 숫자를 매겨야 하죠 (보통의 리모컨을 생각해 보시면 될 것 같습니다.)

- 그래서 생각해낸 것은 바로.....!

- 1. 일단 -1로 모든번호를 저장할 테이블들을 모두 초기화 ! (위로 갔다가 -로 돌아오는 경우도 있으므로 백만까지)

- 2. 버튼으로 이동할 수 있는 번호의 경우 테이블에 미리 다 몇번의 버튼을 눌러서 갈 수 있는지 저장!!!!

- 3. 찾고자 하는 채널이 -1, 즉 버튼만으로 갈 수 없는 경우 위,아래로 탐색해서 가장 가까이 있는 버튼으로 갈 수 있는

      번호를 찾는다 !!!!!!

( 물론 상기의 과정 중 +,- 버튼만으로 가는 것이 더 적은 수로 이동할 수 있는 경우 그 숫자를 넣어줘야 합니다.)

2. 주의사항

- 리모콘은 고장나면 쫌 사자.....

3. 나의코드

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

int N,M;
int remote[10]; //0~9
int casestore[1000001];
int len;

bool onlynum(int num) {
	len = 0;
	int tmp = num;
	while (1) {
		if (remote[tmp % 10] == true) return false; //고장나서 버튼만으로는 이동불가
		tmp /= 10;
		len++;
		if (tmp == 0) break;
	}
	return true;
}
void inputs() {
	cin >> N >> M;
	int tmp;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		remote[tmp] = true; //true는 고장
	}
}
void makecase() {
	casestore[100] = 0;
	for (int i = 0; i < 1000001; i++) {
		if (i == 100) continue;
		if(onlynum(i)==true)
		{
			casestore[i] = min(abs(i - 100), len);
		}
	}
}
void setcase() {
	for (int i = 0; i < 1000001; i++) {
		casestore[i] = -1;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	setcase();
	makecase();

	if (N == 100) { cout << 0 << "\n"; return 0; }
	if(casestore[N]!=-1){
		cout << casestore[N] << "\n"; return 0;
	}
	else{
		int index = 1;
		while (1) {
			if (N - index >= 0) {
				if (casestore[N - index] != -1) {
					cout << min(abs(N - 100),casestore[N - index] + index) << "\n";
					return 0;
				}
			}
			if (N + index <= 1000000) {
				if (casestore[N + index] != -1) {
					cout << min(abs(N - 100),casestore[N + index] + index) << "\n";
					return 0;
				}
			}
			index++;
		}
	}
	return 0;
}

www.acmicpc.net/problem/11048

1. 풀이방법

- 다이나믹프로그래밍을 이용해서 탑다운 방식으로 해결하였습니다.

- 저 같은 경우 1행의 모든 값과 1열의 모든 값들은 가로 또는 세로로 쭉 이동하는 경우밖에 없으므로

- 초기화할 때 먼저 쭉 작업을 해서 dp 테이블에 넣어놓은 후 시작하였습니다.

2. 주의사항

- 주의사항은 아니고 풀고난 후에 생각난 건데 얻을 수 있는 최대의 사탕의 수를 구하는 것이므로

- 대각선 이동은 빼도 될 것 같습니다.

- 사탕을 뺏어간다는 조건이 있지 않은 이상 대각선이 가로->세로, 또는 세로->가로 로 이동하는 것 보다 많은 사탕을 얻을 수는 없기 때문에 사실 확인하지 않아도 될 것입니다.

3. 나의코드

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

int N, M;
int candymap[1001][10001];
int dp[1001][1001];

void inputs() {//기본셋팅
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> candymap[i][j];
			dp[i][j] = -1; //dp테이블은 -1로 초기화
		}
	}
	dp[1][1] = candymap[1][1];
	for (int i = 2; i <= N; i++) {
		dp[i][1] = dp[i - 1][1]+candymap[i][1];
	}
	for (int j = 2; j <= N; j++) {
		dp[1][j] = dp[1][j-1]+candymap[1][j];
	}
}
int maxthree(int num1, int num2, int num3) {
	int tmp = max(num1, num2);
	tmp = max(tmp, num3);
	return tmp;
}
int getdp(int x, int y) {
	if (dp[x][y] != -1) return dp[x][y];
	else {
		dp[x][y] = maxthree(getdp(x - 1, y), getdp(x, y - 1), getdp(x - 1, y - 1))+candymap[x][y];
		return dp[x][y];
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	cout << getdp(N,M) << "\n";
	return 0;
}

www.acmicpc.net/problem/11726

1. 풀이방법

- 이 문제를 접할 때 점화식을 생각해내는 게 생각보다 어려웠습니다.

- 물론 이런 류의 문제는 알고나면 매우 간단하기는 하지만......!

- 결국 점화식은 dp[n]=dp[n-1] + dp[n-2] 입니다 

- 그림을 보시면 이해가 쉬우실 듯 합니다.

2. 주의사항

- 값을 저장할 테이블을 구성해서 메모이제이션을 활용하여 시간을 단축시켜주었습니다.

- 탑다운 방식으로 재귀함수만을 이용하여 연산하는 경우 중복되는 연산을 너무나 많이 하기때문에

- TIME LIMIT을 만나실 수 있습니다.

- 저장되어있는값이 있으면 바로 리턴해서 가져다 쓰고 새로운 값이면 테이블에 저장을 한 후 리턴해서

- 다음부터는 그 값이 필요할 때 테이블에서 바로 가져다 쓸 수 있도록 하면 됩니다.

3. 나의코드

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

int  n;
int dp[1001];

int getdpvalue(int num) {
	if (dp[num] == 0) { 
		dp[num] = (getdpvalue(num - 1) % 10007 + getdpvalue(num - 2) % 10007);
		return dp[num] % 10007;
	}
	else return dp[num]%10007;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	dp[1] = 1; dp[2] = 2; dp[3] = 3; // 3을 초기화안해줘도 되긴하다
	                                 // (하지만 경우의수 그림 그려놨으니까..아까워서)
	cout<<getdpvalue(n)<<"\n";

	return 0;
}

www.acmicpc.net/problem/15684

1. 풀이방법

- 일단 사다리에 대한 표현을 어떻게 할까 고민하다가 저는 char 2차원배열을 선언해서 'R' 또는 'L' 을 넣어서

- 오른쪽으로 가는 경우, 왼쪽으로 가는 경우를 구현했습니다.

- 그렇게 선언한 후 어떤식으로 찾을 까 고민을 하다가(약간 막막)

- 추가하는 최대 line의 수가 3보다 많아지면 그냥 -1을 출력하라는 조건을 보고 아 dfs를 돌리는데 깊이가 3보다 커지

- 면 return을 하는 식으로 구현해야겠다 ( 깊이 3정도니까 전체를 다 보아도 시간초과가 안나겠지???) 라는 생각...!!

2. 주의사항

- 저 같은 경우 아주 초보적인 실수를 했는데 코드에도 주석으로 달아 놓겠지만.....

- 2차원배열로 dfs를 돌때!!

- for(int i=x;i<....){

        for(int j=y;j<....{

                     function (i,j+1,cnt+1);       

                  }

            }

-이런식으로 했다가 헤맸습니다... 이러면 안쪽반복문을 i가 갱신될때는 0부터 돌아야하는데 계속 y부터만 돌게 됩니다

- 저는 안쪽반복문은 그냥 계속 0부터 돌게끔 수정했습니다....(그래서인지 다른 사람들보다는 시간이 약간 길게 걸린 듯)

3. 나의코드

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

int N, M, H;
char sadari[31][11];
int a, b;
int minresult=4; //3 이하; 그 이상은 -1;
bool suc = false;

void inputs() {
	cin >> N >> M >> H;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		sadari[a][b] = 'R';
		sadari[a][b + 1] = 'L';
	}
}
bool checkingright() {
	for (int i = 1; i <= N; i++) {
		int resultcount = i;
		for (int j = 1; j <= H; j++){
			if (sadari[j][i] == 'R') i++;
			else if(sadari[j][i]=='L') i--;
			else continue;
		}
		if (resultcount != i) return false;
		i = resultcount;
	}
	return true;
}
void findline(int x,int cnt) {
	if (cnt > 3) { return; } 
	if (checkingright() == true) {
		if (minresult > cnt) { minresult = cnt; }
		suc = true;
		return;
	}; //성공
	for (int a = x; a < N; a++) {
		for (int b = 1; b <= H; b++) {// for(int b=y;b<=H;b++) xxxxxxxxxx!
			if (sadari[b][a] != 0 || sadari[b][a+1]!=0) continue; //이미 연결되어있음
			else {
				sadari[b][a] = 'R';
				sadari[b][a + 1] = 'L';

				findline(a,cnt + 1);  //findline(a,b+1,cnt+1) xxxxxxxx!

				sadari[b][a + 1] = 0;
				sadari[b][a] = 0;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	findline(1,0);
	if (suc == false) { cout << -1 << "\n"; }
	else cout << minresult << "\n";
	return 0;
}