대엉코딩

www.acmicpc.net/problem/10993

1. 풀이방법

- 재귀를 이용한 별찍기 문제입니다.

- 보통의 별 찍기 문제는 반복문 활용 이고

- 조금 난이도가 있는 별찍기 문제는 재귀+반복문 사용 인경우 가 있습니다.

- 가로와 세로의 길이 (n에따른)  를 먼저 구하고 재귀로 구현하면 되는 문제였습니다.

- 가로는 2^(n+1)-1, 세로는 2^n-1 이였습니다.

- 저는 starmap을 문제 조건 n에 따른 최대치 이상을 이차원 배열로 먼저 선언하였습니다.

2. 주의사항

- 처음 제출하고 "출력형식이 잘못되었습니다" 가 나와 스크롤을 해보았습니다.

-

- 위의 캡처와 같이 바깥쪽 공백은 출력을 하면 안됩니다.

- 저는 이미 이차원배열에 ' '까지 모두 들어가도록 짜서 그냥 출력부에서 홀수,짝수 나누어서 조정해주었습니다.

3. 나의코드

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

int n;
char starmap[2048][2048];

int gety(int n) {
	int fi = 2;
	for (int i = 0; i < n; i++) {
		fi *= 2;
	}
	return (fi - 3);
}
int getx(int n) {
	int fi = 2;
	for (int i = 0; i < n - 1; i++) {
		fi *= 2;
	}
	return (fi - 1);
}

void makestar(int cnt,int startx,int starty) {
	if (cnt == 0) {
		return;
	}
	int cx = getx(cnt);
	int cy = gety(cnt);
	if (cnt % 2 == 0) { //짝수일때 역삼각형
		for (int i = startx; i < startx+cx; i++) {
			for (int j = starty; j <starty+ cy / 2 + 1; j++) {
				if (i == startx) starmap[i][j] = '*';
				else if (j == starty+(i-startx)) starmap[i][j] = '*';
				else starmap[i][j] = ' ';
			}
		}
		for (int i = startx; i < startx+cx; i++) {
			for (int j = starty+cy / 2+1; j < starty+cy; j++) {
				if (i == startx) starmap[i][j] = '*';
				else if (j == starty+cy - 1 - (i-startx)) starmap[i][j] = '*';
				else starmap[i][j] = ' ';
			}
		}
		makestar(cnt - 1, startx +1, starty + cy / 4+1);
	}
	else { //홀수
		for (int i = startx; i <startx+cx; i++) {
			for (int j = starty; j <starty+ cy / 2 + 1; j++) {
				if (i == startx+cx-1) starmap[i][j] = '*';
				else if (j == starty+(cy / 2) - (i-startx)) starmap[i][j] = '*';
				else starmap[i][j] = ' ';
			}
		}
		for (int i = startx; i <startx+cx; i++) {
			for (int j =starty+ cy / 2+1; j <starty+ cy; j++) {
				if (i ==startx+ cx - 1) starmap[i][j] = '*';
				else if (j == starty+(cy / 2) + (i-startx)) starmap[i][j] = '*';
				else starmap[i][j] = ' ';
			}
		}
		makestar(cnt - 1, startx + cx / 2, starty + cy / 4+1);
	}
}
void printstar(int n) {
	int x = getx(n);
	int y = gety(n);
	if (n % 2 == 1) { // 홀수
		for (int i = 0; i < x; i++) {
			for (int j = 0; j <= y/2+i; j++) {
				cout << starmap[i][j];
			}
			cout << "\n";
		}
	}
	else { //짝수
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y - i; j++) {
				cout << starmap[i][j];
			}
			cout << "\n";
		}
	}
}

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


	cin >> n;
	makestar(n, 0, 0);

	printstar(n);

	return 0;
}

- 별찍기 문제의 장점 !   (풀고나서 출력하면 뿌듯하다)

www.acmicpc.net/problem/18511

1. 풀이방법

- 처음 문제를 보고 눈에 띈 숫자는 N이 최대 100,000,000 이므로 선형적으로 증가시켜가며 N과 비교하면 시간초과

- 그러면 주어진 집합을 보고 숫자를 구성해서 N과 비교를 해야 겠다.

- 그래서 자릿수 계산하고 앞자리 수 부터 비교를 해 가면서 어떤 원소를 자릿수에 넣고 해야겠다~~ 라면서 하다보니

- 되게 다양한 경우의 수가 있고 생각보다 너무 복잡하였습니다.....하

- 그래서 문제를 다시 읽어보니..... 매우 쉬워지는 이유가 하나 있었습니다 K의 원소의 개수가 최대 3개 라는 것....!

- 저는 K의 집합 원소가 1~9 이고 집합의 원소의 수 도 역시 최대 10개라고 당연시? 생각해서...

- 이 모두를 조합하는 수는 너무 많다 라고 생각했었는데 아니였습니다...

- 최대 3개 이므로 그냥 모든 조합을 만들어 내서 N가 비교하고 N보다 작거나 같을경우의 수를 모두 벡터에 넣고

- 그 중 최대값을 출력하였습니다.

2. 주의사항

- 문제를 똑바로 파악하고 시작할 것 !!!!

3. 나의코드

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

int n, k,tmp;
vector<int> numarr;
vector<int> resultarr; //n을 쪼개놓자

bool compare(int& lhs, int& rhs) {
	if (lhs > rhs) return true;
	else return false;
}

void makecase(int num,int cnt) {
	if (cnt!=0 && num <= n) { 
		resultarr.emplace_back(num);
	}
	if (num > n) return;
	for (int i = 0; i < k; i++) {
		if (cnt == 0) { makecase(num * numarr[i],cnt+1); }
		else makecase(num*10+numarr[i],cnt+1);
	}
}

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

	cin >> n >> k;
	
	for (int i = 0; i < k; i++) {
		cin >> tmp;
		numarr.emplace_back(tmp);
	}
	sort(numarr.begin(), numarr.end(), compare);
	makecase(1,0);
	sort(resultarr.begin(), resultarr.end(), compare);
	cout << resultarr[0];
	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;
}

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

- dfs 를 이용한 완전 탐색 문제였습니다. (백트래킹 이라고도 하는...)

- 사실 저는 백트래킹이라는 개념을 딱히 그렇게 정의지어 배워본 적이 없어서 다른 문제하나를 풀다가

- 접한적은 있습니다만....

- 이문제는 dfs 느낌과 비슷하게 재귀를 이용 하여 모든 경우의 수를 모두 탐색 하는 방향으로 해결하였습니다.

- 다른건 어려운 것이 없고 최대20 명이 되는 n을 두팀에 나누어 넣는 모든 경우의 수를 어떻게 구현해 내는지가

- 핵심이였던 문제인 것 같습니다..

<코드>

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

dfs라고 보면 dfs인 것 같기도 한데

많은 분들이 dfs와 백트래킹 이라고 많이 하시던데 그렇게들 푸시고

아직 이에대한 개념이 충분치 않아서....... 좀 오래걸리기도 했고 사실 아직도 잘 모르겠습니다...

다른분들의 코드도 보고 참고 하였습니다. 

일단은 이해를 하는 것을 우선으로 두기로 하였습니다........... 공부 해야겠네요....

저처럼 이해가 안되실 분 들을 위해 가능한 쉽게 제가 이해한 방식을 올리겠습니다.

<필기>

<코드>