okayoki

ba#문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

#작성 코드

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

int N;
int num[12];
int op[4];
// 결과의 최댓값과 최솟값은 절댓값 10억을 넘지 않는다. 
int ret_min = 1000000001, ret_max=-1000000001;

void answer(int result, int count){
	if( count==N-1 ){
		if(ret_min>result)
			ret_min = result;
		if(ret_max<result)
			ret_max = result;
		return;
	}
	
	// N개의 수로 이루어진 수열에 대해 연산 진행.
	// N-1개의 연산자 
	for(int i=0; i<4; i++){
		if( op[i]>0 ){
			op[i]--;
			
			if(i==0){
			answer(result+num[count+1], count+1);
			}
			if(i==1){
			answer(result-num[count+1], count+1);
			}
			if(i==2){
			answer(result*num[count+1], count+1);
			}
			if(i==3){
			answer(result/num[count+1], count+1);
			}
			
			op[i]++;
		}
	}
}

int main(){
	// 숫자의 개수, 수열 입력 
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", &num[i]);
	}
	// 연산자의 개수 입력. + - * / 순서 
	for(int i=0; i<4; i++){
		scanf("%d", &op[i]);
	}
	
	answer(num[0], 0);
	// 최댓값, 최솟값 출력 
	printf("%d\n%d", ret_max, ret_min);
	return 0;
} 

##

#작성 코드

#include <cstdio>
#include <cstdlib>

// 모두 비워진 스도쿠 판 준비 
int sdoku[9][9];

// 행, 열, 3x3블록에 각 숫자가 존재하는지 체크할 bool 배열
bool checkR[9][10];
bool checkC[9][10];
bool checkS[9][10];

int zeros[81];
int n;

int fx(int i, int j){
	return i/3*3+j/3;
}

void solve(int idx){
    if( idx==n ){
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                printf("%d ", sdoku[i][j]);
            }
            printf("\n");
        }
        exit(0);
    }
	int x = zeros[idx]/9;
	int y = zeros[idx]%9;
	
	for(int num=1; num<10; num++){
		// 행, 열, 3x3블록에 해당 숫자가 존재하면 다음 수로 넘어간다  
		if( checkR[x][num] || checkC[y][num] || checkS[fx(x, y)][num] )
			continue;
		checkR[x][num] = checkC[y][num] = checkS[fx(x, y)][num] = true;
		sdoku[x][y] = num;
		solve(idx+1);		// dfs 
		sdoku[x][y] = 0;	// 백트래킹 
		checkR[x][num] = checkC[y][num] = checkS[fx(x, y)][num] = false;
	}
}

int main()
{
	for (int i=0; i<9; i++) {
        for (int j=0; j<9; j++) {
            scanf("%d", &sdoku[i][j]);
            int tmp = sdoku[i][j];
            if (!tmp) zeros[n++] = i*9+j;
            else {
                checkR[i][tmp] = true;
                checkC[j][tmp] = true;
                checkS[fx(i,j)][tmp] = true;
            }
        }
    }
    solve(0);
    return 0;
}

##

#작성 코드

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

int N;
int count;			// 퀸을 놓을 수 있는 방법의 수 
bool col[15];		// 인덱스 : 열의 번호. 이 열에 퀸이 존재하는가. 
bool *dup;
bool *ddown;

void findQueen(int n){
	if( n==N ){		// n은 행을 가리킴. 0~n-1까지 조사 완료했으면 
		count++;	// count 증가 
	}
	else{
		for(int i=0; i<N; i++){
			if( col[i] ) continue;
			if( dup[n+i] || ddown[N-1+n-i]) continue;
			col[i] = dup[n+i] = ddown[N-1+n-i] = true;
			findQueen(n+1);
			col[i] = dup[n+i] = ddown[N-1+n-i] = false;
		}
	} 
}

int main(){
	scanf("%d", &N);
	dup = new bool[2*N-1];
	ddown = new bool[2*N-1];
	
	findQueen(0);
	
	printf("%d", count);		// 퀸을 놓을 수 있는 방법의 수 출력 
	delete[] dup;
	delete[] ddown;
	return 0;
}

아래는 (n, i)위치에 퀸을 배치할 수 있는지 체크하는 함수를 사용한 코드인데, 아직 완성하지 못했다.

#include <iostream>
using namespace std;

int N;
int count;
bool *arr;
bool *dup;
bool *ddown;

//bool promising(int n, int i){
//	bool flag = true;
//	int k=0;
//	while( k<i && flag ){
//		if( arr[k]==true ) flag = false;
//		if( dup[n+k] == true || ddown[N-1+n-k]==true ) flag = false;
//	}
//	return flag;
//}

void findQueen(int n){
	if( n>=N ) count++;
	  
	for(int i=0; i<N; i++){		// (n, x)에 퀸을 배치할수있는지 체크
		if( arr[i]==true ) continue;
		if( dup[n+i] == true || ddown[N-1+n-i]==true ) continue;
		arr[i] = dup[n+i] = ddown[N-1+n-i] = true;
		findQueen(n+1);
		arr[i] = dup[n+i] = ddown[N-1+n-i] = false;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>N;
	
	arr = new bool[N];
	dup = new bool[2*N-1];
	ddown = new bool[2*N-1];
	
	findQueen(0);
	cout<<count;
	
	delete[] arr;
	delete[] dup;
	delete[] ddown;
	return 0;
}

##

findQueen 함수 내에서 현재 위치가 퀸을 놓기에 적절한 위치인지 promising함수로 체크하려고 했는데 이렇게 하면 (n, i)를 체크하면서 i에 따라 인덱스 0부터 i까지 체크하게 돼서 비효율적이다.

/ 방향 대각선은 행과 열의 합으로 구분할 수 있고,

\ 방향 대각선은 행-열이 n=3인 경우에 2, 1, 0, -1, -2 로 나타나므로 n-1을 더해주면 4, 3, 2, 1, 0으로 표현할 수 있다.

#작성 코드

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

int N, M;
int visit[9];
vector<int> v;

void dfs(int a, int cnt){
	if( cnt == M ){
		for(int i=0; i<v.size()-1; i++){
			if( v[i]>v[i+1] ) return;		//비내림차순만 출력 
		}
		for(int i=0; i<v.size(); i++){
			cout<<v[i]<<' ';
		}
		cout<<'\n';
		return;		// 출력 후에는 dfs함수를 반드시 종료시켜야한다 
	}
	
	for(int i=a+1; i<=N; i++){
		if( visit[i]==M ) continue;	// 최대 M번까지 방문할 수 있도록 
		visit[i]++;
		v.push_back(i);
		dfs(a, cnt+1);
		visit[i]--;
		v.pop_back();
	}
}

int main(){
	cin>>N>>M;
	dfs(0, 0);
	return 0;
}  

##

15651번 N과 M(3)번과 유사하지만 '중복 조합'을 출력해야 했다.

cnt==M일 때 출력하게되는데 이 때 벡터 v에 대해 v[i]>v[i+1]인지 조사하여 비내림차순이 확정되면 출력하고, 아니면 dfs함수를 종료하도록 했다.

조합을 출력하는 15650번과의 다른점은 dfs를 재귀호출할 때 dfs(a, cnt+1)으로 재귀호출한다는 것이다.

조합을 출력할 때는 for( int i=a+1; i<=N; i++){ ... dfs(i, cnt+1) ... } 으로 재귀호출했었지만 중복으로 선택하기 위해서는 한 번 체크했던 a+1번째에 다시 방문해야하므로 중복조합을 찾을 때는 dfs(a, cnt+1)으로 재귀호출한다.

#작성 코드

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

int N, M;
int visit[8];
vector<int> v;

void dfs(int cnt){
	if( cnt == M ){
		for(int i=0; i<v.size(); i++){
			cout<<v[i]<<' ';
		}
		cout<<'\n';
		return;		// 출력 후에는 dfs함수를 반드시 종료시켜야한다 
	}
	
	for(int i=1; i<=N; i++){
		if( visit[i]==M ) continue;	// 최대 M번까지 방문할 수 있도록 
		visit[i]++;
		v.push_back(i);
		dfs(cnt+1);
		visit[i]--;
		v.pop_back();
	}
}

int main(){
	cin>>N>>M;
	dfs(0);
	return 0;
} 

##

앞의 문제들과 달리 중복순열을 구해야 한다.

visit배열을 int 형 배열로 선언하여 한 숫자를 최대 M번 사용할 수 있도록 했다.

#작성 코드

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

int N, M;
vector<int> v;
bool visit[9];

void dfs(int idx, int cnt){
	if( cnt == M ){
		for(int i=0; i<v.size(); i++){
			cout<<v[i]<<' ';
		}
		cout<<'\n';
	}
	
	for(int i=idx+1; i<=N; i++){
		if( visit[i] == true ){
			continue;
		}
		visit[i] = true;
		v.push_back(i);
		dfs(i, cnt+1);
		visit[i] = false;
		v.pop_back();
	}
}
int main(){
	cin>>N>>M;
	dfs(0, 0);
	return 0;
}

##

앞의 15649문제와 다른 점은 오름차순으로 중복 없는 순열을 출력해야 한다는 것이다.

=> DFS호출시에 현재 idx를 매개변수로 함께 넣어줘서 방문할 숫자를 해당 dfs의 idx에서부터 시작하도록 하였다.

dfs(0, 0)으로 호출했으므로 자연수 1부터 방문해야하니까 i = idx+1 ~ i<=N