대엉코딩

www.acmicpc.net/problem/14500

1. 문제풀이 방법

- 테트리스에 너무 익숙한 탓일까요....?

- 문제조건에서 대칭을 시켜도 된다는 조건을 빼먹고...이건 뭐 아이디어가 안떠올라서 모든 좌표탐색을 했으나

- 대칭을 안넣었으니...당연히 틀릴 수 밖에 없었습니다....

- 문제 조건을 다시 파악하고 보니 DFS 깊이 4짜리에 해당하는 모든 좌표가 테트로미노로 표현이 된다는 것을

  알아내었습니다....

- 하지만 ㅗ ㅏ ㅜ ㅓ 는 DFS로 표현이 불가능 합니다 (집합느낌으로 보면 테트로미노 > 4짜리 DFS?) 이런느낌?

- 그래서 그건 따로 직접 좌표를 설정해 구해주었습니다.

2. 주의사항

- 문제를 똑바로 파악하자!!!!

3. 나의코드

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

int N, M;
int tetro[501][501];
int maxvalue = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool visit[501][501];
int depth = 0;
int tmpsum;

void dfs(int x, int y) {
	if (depth == 4) {
		if (tmpsum > maxvalue) maxvalue = tmpsum;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int x2 = x + dx[i];
		int y2 = y + dy[i];
		if (x2 >= 0 && x2 < N &&y2 >= 0 && y2 < M && visit[x2][y2]==false) {
			visit[x2][y2] = true;
			depth++;
			tmpsum += tetro[x2][y2];
			dfs(x2, y2);
			tmpsum -= tetro[x2][y2];
			depth--;
			visit[x2][y2] = false;
		}
	}
}

void cantdfs(int x, int y)
{
	int result = 0;
	if (x - 1 >= 0 && y + 2 < M) {// ㅗ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x][y + 2] + tetro[x - 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 1 < N &&y + 2 < M) { // ㅜ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x][y + 2] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 1 < N &&x - 1 >= 0 && y + 1 < M) { // ㅓ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x - 1][y + 1] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 2 < N &&y + 1 < M) {
		result = tetro[x][y] + tetro[x + 1][y] + tetro[x + 2][y] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> tetro[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			depth = 1;
			tmpsum = tetro[i][j];
			visit[i][j] = true;
			dfs(i, j);
			visit[i][j] = false;
			cantdfs(i, j);
		}
	}
	cout << maxvalue << "\n";

	return 0;
}

www.acmicpc.net/problem/14890

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;
}

www.acmicpc.net/problem/15686

1. 풀이방법

- 문제를 꼼꼼히 읽고, 전체 치킨 집 중에서 M개를 선택하는 경우의 수 (조합)

- 을 구해서 그 CASE마다 도시의 치킨거리를 구해보면 되는 문제.

2. 주의할점

- 딱히없음.

3.나의 코드

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

int N, M;
int map[51][51];
vector<pair<int, int>> chikenstore; //전체 치킨집을 저장할 좌표 집합
vector<pair<int, int>> chosenstore; //선택된 치킨집을 저장할 좌표 집합(M개)
vector<pair<int, int>> home; //집의 위치를 저장할 좌표 집합 (x,y) 
vector<int> result; //결과

void InputMap() { //입력받는 함수
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				pair<int, int> tmp;
				tmp.first = i; tmp.second = j;
				chikenstore.push_back(tmp);
			}
			else if (map[i][j] == 1) {
				pair<int, int> tmp;
				tmp.first = i; tmp.second = j;
				home.push_back(tmp);
			}
		}
	}
}

int abs(int num1, int num2) { //절대값 반환
	if (num1 - num2 > 0) { return num1 - num2; }
	else { return num2 - num1; }
}

int loadsum(int x1, int y1, int x2, int y2) { //거리 계산
	return abs(x1, x2) + abs(y1, y2);
}

void caculatechickenload() { //도시의 치킨거리를 계산
	int sum = 0;
	for (int i = 0; i < home.size(); i++) { //집마다
		int min = 3000;
		for (int j = 0; j < chosenstore.size(); j++) { //치킨집에 대하여 거리계산(가장 가까운 치킨집=치킨거리)
			if (min > loadsum(home[i].first, home[i].second, chosenstore[j].first, chosenstore[j].second)) {
				min = loadsum(home[i].first, home[i].second, chosenstore[j].first, chosenstore[j].second);
			}
		}
		sum += min;
	}
	result.push_back(sum);
}

void Mchickenstore(int index) {
	if (chosenstore.size() == M) { // M개를 골랐다면 치킨거리계산 시작
		caculatechickenload();
		return;
	}
	for (int i = index; i < chikenstore.size(); i++) { //조합 경우의 수
		chosenstore.push_back(chikenstore[i]);
		Mchickenstore(i + 1);
		chosenstore.pop_back();
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	InputMap();
	Mchickenstore(0);
	sort(result.begin(), result.end()); //가장 최소 도시치킨거리 출력
	cout << result[0] << "\n";
	
	return 0;
}

www.acmicpc.net/problem/3190

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;
}

www.acmicpc.net/problem/18406

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;
}

www.acmicpc.net/problem/17070

- 완전탐색을 문제 조건에 맞게 구현하여 경우의 수를 구하면 되는 간단한 문제이다.

- CASE는 방법에 따른 이동을 순열로 구하면 되는데 현재 파이프가 어떻게 놓여져 있는 지 에 따라 사용 가능한 이동방법이 다르므로 그것만 분류해주면 된다.

-direction 은 0은 가로, 1은 세로 , 2는 대각선이고

 case 1~7의 경우 문제에 표기된 그림의 순서 그대로 사용하였다.

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

int totalcount=0;
int housemap[17][17];
int N;
int x=1;
int y=2;
int dx[3] = { 0,1,1 }; //가로,세로,대각선이동
int dy[3] = { 1,0,1 };
int direction = 0; // 가로,세로,대각선 방향
void startsearch(int x,int y,int d) {
	if (x > N || y > N) return; //종료조건(미도착)
	if (x == N && y == N) { totalcount++; return; } //종료조건(도착
	if (d == 0) {
		if (housemap[x + dx[0]][y + dy[0]] != 1) 
		startsearch(x + dx[0], y + dy[0], 0); //case 1
		if (housemap[x + dx[2]][y + dy[2]] != 1 && housemap[x + dx[1]][y + dy[1]] != 1 && housemap[x + dx[0]][y + dy[0]] != 1) 
		startsearch(x + dx[2], y + dy[2], 2); //case 2
	}
	else if (d == 1) {
		if (housemap[x + dx[1]][y + dy[1]] != 1) 
		startsearch(x + dx[1], y + dy[1], 1); //case 3
		if (housemap[x + dx[2]][y + dy[2]] != 1 && housemap[x + dx[1]][y + dy[1]] != 1 && housemap[x + dx[0]][y + dy[0]] != 1)
		startsearch(x + dx[2], y + dy[2], 2); //case 4
	}
	else {
		if (housemap[x + dx[0]][y + dy[0]] != 1)
		startsearch(x + dx[0], y + dy[0], 0); //case 5
		if (housemap[x + dx[1]][y + dy[1]] != 1) 
		startsearch(x + dx[1], y + dy[1], 1); //case 6
		if (housemap[x + dx[2]][y + dy[2]] != 1 && housemap[x + dx[1]][y + dy[1]] != 1 && housemap[x + dx[0]][y + dy[0]] != 1) 
		startsearch(x + dx[2], y + dy[2], 2); //case 7
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> housemap[i][j];
		}
	}
	if (housemap[N][N]!=1) { startsearch(x, y, direction); }
	cout << totalcount << "\n";
	return 0;
}

www.acmicpc.net/problem/17281

- 모든 가능한 순열 case를 모두 구해서 야구 시뮬레이션을 돌려서 가장 큰 점수를 반환해주면 됩니다.

-순열 case만 제대로 모두 구한다면 야구게임 자체를 구현하는 것은 어렵지 않습니다.

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

int N;
bool playerordercheck[10];
int playerresult[51][10];
int playerorder[10];
bool location[4]; //1루 2루 3루 를 표시
int resultscore;
int maxscore;
void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for(int j=1;j<=9;j++){
			cin >> playerresult[i][j];
		}
	}
}
void resetlocation() { //1,2,3루 초기화
	for (int i = 1; i <= 3; i++) {
		location[i] = false;
	}
	return;
}
void getscorecheck(int num) {
	for (int i = 3; i >= 1; i--) {
		if (location[i] == true) {
			if (i + num >= 4) { location[i] = false; resultscore++; }
			else { location[i] = false; location[i + num] = true; } //주자 이동
		}
	}
	if (num >= 4) { resultscore++; return; } //홈런인 경우
	else { location[num] = true; return; }
}
int gamestart() {
	resultscore = 0;
	int outcount = 0;
	int playerpointer = 1;
	for (int i = 1; i <= N; i++) { //N이닝동안 반복
		outcount = 0; //이닝별 아웃카운터 초기화
		while (1) { //주자 한명씩 확인
			if (outcount == 3) {
				resetlocation(); //나가있던 주자들 모두 들어옴.
				break;
			}
			if (playerresult[i][playerorder[playerpointer]] == 1) { //1루타
				getscorecheck(1);
			}
			else if (playerresult[i][playerorder[playerpointer]] == 2) {//2루타
				getscorecheck(2);
			}
			else if (playerresult[i][playerorder[playerpointer]] == 3) {//3루타
				getscorecheck(3);
			}
			else if (playerresult[i][playerorder[playerpointer]] == 4) {//4루타
				getscorecheck(4);
			}
			else { //아웃된 경우
				outcount++;
			}
			playerpointer++;
			if (playerpointer == 10) { playerpointer = 1; } //9번 주자까지 다 치면 다시 1번 주자
		}
	}
	return resultscore;
}
void P(int cnt) {
	if (cnt == 10) {
		int tmp = gamestart();
		if (maxscore < tmp) { //각 case가 확정되면 게임을 시작한다.
			maxscore = tmp;
		} 
		return;
	}
	for (int i = 1; i <= 9; i++) {
		if (playerordercheck[i] == true) continue;//아직 배정되지 않은 선수라면playerordercheck[i] = true;
		playerordercheck[i] = true;
		playerorder[i] = cnt;
		P(cnt + 1); //모든 순열case을 찾자
		playerordercheck[i] = false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	input();
	playerordercheck[4] = true; //4번타자는 1번으로 고정(문제조건) -이미 자리가 배정됨
	playerorder[4] = 1;
	P(2); //1명은 이미 자리 배정이 완료되었음으로... permutation(순열)
	      //순서를 고려해야함
	cout << maxscore << "\n";

	return 0;
}

https://www.acmicpc.net/problem/1764

그냥 모든 경우의 수를 입력 받은 후 (듣지 못하는 사람) 을 보지 못하는 사람을 입력받을 때 

듣지 못하는 사람 전체와 비교를 하면 시간 초과가 뜹니다 (n,m이 무려 500,000이기 때문에 )

그래서 오랜만에 binarysearch를 직접 구현하여 문제를 해결 하였습니다.

그리고 문제에서 사전 순 배열을 원하였으므로 중간에 sort를 사용하시면 됩니다.