728x90
 

11050번: 이항 계수 1

첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\))

www.acmicpc.net

#include <iostream>
using namespace std;


int main() {
	int n, k;
	cin >> n >> k;
	int numerator = 1; //분자
	int denominator = 1; //분모
	for (int i = n; i > n - k; i--) {
		numerator *= i;
	}
	for (int i = k; i >= 1; i--) {
		denominator *= i;
	}
	cout << numerator / denominator;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 6603번 로또  (0) 2020.01.29
[백준] 1181번 단어 정렬  (0) 2020.01.29
[백준] 1065번 한수  (0) 2020.01.28
[백준] 17144번 미세먼지 안녕!  (0) 2020.01.28
[백준] 14891번 톱니바퀴  (0) 2020.01.27
728x90

단계별로 풀어보기 함수의 3단계 문제이다.

 

1065번: 한수

어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 

www.acmicpc.net

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


int main() {
	int n;
	cin >> n;
	int count = 0;
	for (int i = 1; i <= n; i++) {
		if (i < 100) {
			count++;
		}
		else if (i < 1000){
			int a, b, c;
			a = i / 100;
			b = i / 10 % 10;
			c = i % 10;
			if (a - b == b - c) count++;
		}
	}
	cout << count << endl;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 1181번 단어 정렬  (0) 2020.01.29
[백준] 11050번 이항계수 1  (0) 2020.01.28
[백준] 17144번 미세먼지 안녕!  (0) 2020.01.28
[백준] 14891번 톱니바퀴  (0) 2020.01.27
[백준] 10809번 알파벳 찾기  (0) 2020.01.26
728x90

삼성 SW 역량 테스트 기출 문제인 17144번 문제

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼

www.acmicpc.net

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


int main() {
	int r, c, t;
	cin >> r >> c >> t;
	int** room = new int*[r];
	int** copyRoom = new int*[r];
	int** spreadRoom = new int*[r];
	for (int i = 0; i < r; i++) {
		room[i] = new int[c];
		copyRoom[i] = new int[c];
		spreadRoom[i] = new int[c];
	}
	pair<int, int> purifier[2];
	int index = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> room[i][j];
			if (room[i][j] == -1) {
				purifier[index] = make_pair(i, j);
				index++;
			}
		}
	}
	for (int time = 0; time < t; time++) {
		if (time != 0) {
			for (int i = 0; i < r; i++) {
				for (int j = 0; j < c; j++) {
					room[i][j] = spreadRoom[i][j];
				}
			}
		}
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				copyRoom[i][j] = room[i][j] / 5;
			}
		}
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				spreadRoom[i][j] = 0;
			}
		}
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				int count = 0;
				if (i - 1 >= 0 && !(i - 1 == purifier[0].first && j == purifier[0].second) && !(i - 1 == purifier[1].first && j == purifier[1].second)) {
					spreadRoom[i - 1][j] += copyRoom[i][j];
					count++;
				}
				if (i + 1 < r && !(i + 1 == purifier[0].first && j == purifier[0].second) && !(i + 1 == purifier[1].first && j == purifier[1].second)) {
					spreadRoom[i + 1][j] += copyRoom[i][j];
					count++;
				}
				if (j - 1 >= 0 && !(i == purifier[0].first && j - 1 == purifier[0].second) && !(i == purifier[1].first && j - 1 == purifier[1].second)) {
					spreadRoom[i][j - 1] += copyRoom[i][j];
					count++;
				}
				if (j + 1 < c && !(i == purifier[0].first && j + 1 == purifier[0].second) && !(i == purifier[1].first && j + 1 == purifier[1].second)) {
					spreadRoom[i][j + 1] += copyRoom[i][j];
					count++;
				}
				spreadRoom[i][j] += room[i][j] - count * copyRoom[i][j];
			}
		}


		int direction = 0; //위는 0, 오른쪽은 1, 아래는 2, 왼쪽은 3
		int row = purifier[0].first - 1;
		int col = purifier[0].second;
		while (true) {
			if (direction == 0) { //위쪽 방향일 때
				if (row - 1 >= 0) {
					spreadRoom[row][col] = spreadRoom[row - 1][col];
					row--;
				}
				else
					direction = 1;
			}
			if (direction == 1) { //오른쪽 방향일 때
				if (col + 1 < c) {
					spreadRoom[row][col] = spreadRoom[row][col + 1];
					col++;
				}
				else
					direction = 2;
			}
			if (direction == 2) { //아래 방향일 때
				if (row + 1 <= purifier[0].first) {
					spreadRoom[row][col] = spreadRoom[row + 1][col];
					row++;
				}
				else direction = 3;
			}
			if (direction == 3) {
				if (col - 1 >= 0) {
					if (spreadRoom[row][col - 1] == -1) {
						spreadRoom[row][col] = 0;
						col--;
						direction = 0;
						break;
					}
					else spreadRoom[row][col] = spreadRoom[row][col - 1];
					col--;
				}
			}
		}


		direction = 0;
		row = purifier[1].first + 1;
		col = purifier[1].second;
		while (true) {
			if (direction == 0) { //아래쪽 방향일 때
				if (row + 1 < r) {
					spreadRoom[row][col] = spreadRoom[row + 1][col];
					row++;
				}
				else
					direction = 1;
			}
			if (direction == 1) { //오른쪽 방향일 때
				if (col + 1 < c) {
					spreadRoom[row][col] = spreadRoom[row][col + 1];
					col++;
				}
				else
					direction = 2;
			}
			if (direction == 2) { //위쪽 방향일 때
				if (row - 1 >= purifier[1].first) {
					spreadRoom[row][col] = spreadRoom[row - 1][col];
					row--;
				}
				else direction = 3;
			}
			if (direction == 3) { //왼쪽 방향일 때
				if (col - 1 >= 0) {
					if (spreadRoom[row][col - 1] == -1) {
						spreadRoom[row][col] = 0;
						col--;
						direction = 0;
						break;
					}
					else spreadRoom[row][col] = spreadRoom[row][col - 1];
					col--;
				}
			}
		}
	}


	int sum = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			sum += spreadRoom[i][j];
		}
	}
	cout << sum + 2 << endl;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 11050번 이항계수 1  (0) 2020.01.28
[백준] 1065번 한수  (0) 2020.01.28
[백준] 14891번 톱니바퀴  (0) 2020.01.27
[백준] 10809번 알파벳 찾기  (0) 2020.01.26
[백준] 14889번 스타트와 링크  (0) 2020.01.25
728x90

삼성 SW 역량 테스트 기출 문제인 14891번 문제

 

14891번: 톱니바퀴

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴

www.acmicpc.net

나보다 더 노가다로 푼 사람이 있을까 싶을 정도다

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


int main() {
	string wheel[4];
	int left[4];
	int right[4];
	for (int i = 0; i < 4; i++) {
		cin >> wheel[i];
		left[i] = 6;
		right[i] = 2;
	}
	int k;
	cin >> k;
	int* wheelNum = new int[k];
	int* direction = new int[k];
	for (int i = 0; i < k; i++) {
		int temp;
		cin >> temp;
		cin >> direction[i];
		wheelNum[i] = temp - 1;
	}
	for (int i = 0; i < k; i++) {
		if (wheelNum[i] == 0) { //0번 톱니바퀴인 경우
			if (direction[i] == 1) { //시계 방향인 경우
				if (wheel[0][right[0]] != wheel[1][left[1]]) { //오른쪽 톱니바퀴(1번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 1번이 시계 반대 방향으로 돌아야 함
					if (wheel[1][right[1]] != wheel[2][left[2]]) { //1번과 2번 톱니바퀴가 맞닿는 부분이 다른 극이면 2번 톱니바퀴가 시계방향으로 돌아야 함
						if (wheel[2][right[2]] != wheel[3][left[3]]) { //2번 톱니바퀴와 3번 톱니바퀴가 맞닿는 부분이 다른 극이면 3번이 시계반대방향으로 돌아야 함
							right[3] = (right[3] + 1) % 8;
							left[3] = (left[3] + 1) % 8;
						}
						right[2] = (right[2] - 1 + 8) % 8;
						left[2] = (left[2] - 1 + 8) % 8;
					}
					left[1] = (left[1] + 1) % 8;
					right[1] = (right[1] + 1) % 8;
				}
				right[0] = (right[0] - 1 + 8) % 8;
				left[0] = (left[0] - 1 + 8) % 8;
			}
			else { //시계 반대 방향인 경우
				if (wheel[0][right[0]] != wheel[1][left[1]]) { //오른쪽 톱니바퀴(1번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 시계 방향으로 돌아야 함
					if (wheel[1][right[1]] != wheel[2][left[2]]) { //1번 톱니바퀴와 2번 톱니바퀴가 맞닿는 부분이 다른 극이면 2번 톱니바퀴가 시계반대방향으로 돌아야 함
						if (wheel[2][right[2]] != wheel[3][left[3]]) { //2번 톱니바퀴와 3번 톱니바퀴가 맞닿는 부분이 다른 극이면 3번이 시계방향으로 돌아야 함
							right[3] = (right[3] - 1 + 8) % 8;
							left[3] = (left[3] - 1 + 8) % 8;
						}
						right[2] = (right[2] + 1) % 8;
						left[2] = (left[2] + 1) % 8;
					}
					left[1] = (left[1] - 1 + 8) % 8;
					right[1] = (right[1] - 1 + 8) % 8;
				}
				right[0] = (right[0] + 1) % 8;
				left[0] = (left[0] + 1) % 8;
			}
		}






		else if (wheelNum[i] == 1) {
			if (direction[i] == 1) { //시계 방향인 경우
				if (wheel[1][right[1]] != wheel[2][left[2]]) { //시계 반대 방향으로 돌아야 함
					if (wheel[2][right[2]] != wheel[3][left[3]]) {
						left[3] = (left[3] - 1 + 8) % 8;
						right[3] = (right[3] - 1 + 8) % 8;
					}
					left[2] = (left[2] + 1) % 8;
					right[2] = (right[2] + 1) % 8;
				}
				if (wheel[0][right[0]] != wheel[1][left[1]]) { //왼쪽 톱니바퀴(0번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 시계 반대 방향으로 돌아야 함
					left[0] = (left[0] + 1) % 8;
					right[0] = (right[0] + 1) % 8;
				}
				right[1] = (right[1] - 1 + 8) % 8;
				left[1] = (left[1] - 1 + 8) % 8;
			}
			else { //1번 톱니바퀴이고 반시계 방향인 경우
				if (wheel[1][right[1]] != wheel[2][left[2]]) { //시계 방향으로 돌아야 함
					if (wheel[2][right[2]] != wheel[3][left[3]]) {
						left[3] = (left[3] + 1) % 8;
						right[3] = (right[3] + 1) % 8;
					}
					left[2] = (left[2] - 1 + 8) % 8;
					right[2] = (right[2] - 1 + 8) % 8;
				}
				if (wheel[0][right[0]] != wheel[1][left[1]]) { //왼쪽 톱니바퀴(0번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 시계 방향으로 돌아야 함
					left[0] = (left[0] - 1 + 8) % 8;
					right[0] = (right[0] - 1 + 8) % 8;
				}
				right[1] = (right[1] + 1) % 8;
				left[1] = (left[1] + 1) % 8;
			}
		}
		else if (wheelNum[i] == 2) { //2번 톱니바퀴인 경우
			if (direction[i] == 1) { //시계 방향인 경우
				if (wheel[2][right[2]] != wheel[3][left[3]]) { //오른쪽 톱니바퀴(3번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 3번 톱니바퀴가 시계 반대 방향으로 돌아야 함
					left[3] = (left[3] + 1) % 8;
					right[3] = (right[3] + 1) % 8;
				}
				if (wheel[2][left[2]] != wheel[1][right[1]]) { //왼쪽 톱니바퀴(1번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 시계 반대 방향으로 돌아야 함
					if (wheel[0][right[0]] != wheel[1][left[1]]) { //0번 톱니바퀴와 1번 톱니바퀴가 맞닿는 부분이 다른 극이면 0번 톱니바퀴가 시계방향으로 돌아야 함
						right[0] = (right[0] - 1 + 8) % 8;
						left[0] = (left[0] - 1 + 8) % 8;
					}
					left[1] = (left[1] + 1) % 8;
					right[1] = (right[1] + 1) % 8;
				}
				right[2] = (right[2] - 1 + 8) % 8;
				left[2] = (left[2] - 1 + 8) % 8;
			}
			else { //2번 톱니바퀴이고 반시계 방향인 경우
				if (wheel[2][right[2]] != wheel[3][left[3]]) { //오른쪽 톱니바퀴(3번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 3번 톱니바퀴가 시계 방향으로 돌아야 함
					left[3] = (left[3] - 1 + 8) % 8;
					right[3] = (right[3] - 1 + 8) % 8;
				}
				if (wheel[2][left[2]] != wheel[1][right[1]]) { //왼쪽 톱니바퀴(1번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 시계 방향으로 돌아야 함
					if (wheel[0][right[0]] != wheel[1][left[1]]) { //0번 톱니바퀴와 1번 톱니바퀴가 맞닿는 부분이 다른 극이면 0번 톱니바퀴가 시계반대방향으로 돌아야 함
						right[0] = (right[0] + 1) % 8;
						left[0] = (left[0] + 1) % 8;
					}
					left[1] = (left[1] - 1 + 8) % 8;
					right[1] = (right[1] - 1 + 8) % 8;
				}
				right[2] = (right[2] + 1) % 8;
				left[2] = (left[2] + 1) % 8;
			}
		}
		else { //3번 톱니바퀴인 경우
			if (direction[i] == 1) { //시계 방향인 경우
				if (wheel[3][left[3]] != wheel[2][right[2]]) { //2가 시계반대 방향으로 돌아야 함
					if (wheel[1][right[1]] != wheel[2][left[2]]) { //1이 시계 방향으로 돌아야 함
						if (wheel[0][right[0]] != wheel[1][left[1]]) { //0이 시계 반대 방향으로 돌아야 함
							right[0] = (right[0] + 1) % 8;
							left[0] = (left[0] + 1) % 8;
						}
						right[1] = (right[1] - 1 + 8) % 8;
						left[1] = (left[1] - 1 + 8) % 8;
					}
					left[2] = (left[2] + 1) % 8;
					right[2] = (right[2] + 1) % 8;
				}
				right[3] = (right[3] - 1 + 8) % 8;
				left[3] = (left[3] - 1 + 8) % 8;
			}
			else { //시계 반대 방향인 경우
				if (wheel[3][left[3]] != wheel[2][right[2]]) { //2가 시계방향으로 돌아야 함
					if (wheel[1][right[1]] != wheel[2][left[2]]) { //1이 시계 반대 방향으로 돌아야 함
						if (wheel[0][right[0]] != wheel[1][left[1]]) { //0이 시계 방향으로 돌아야 함
							right[0] = (right[0] - 1 + 8) % 8;
							left[0] = (left[0] - 1 + 8) % 8;
						}
						right[1] = (right[1] + 1) % 8;
						left[1] = (left[1] + 1) % 8;
					}
					left[2] = (left[2] - 1 + 8) % 8;
					right[2] = (right[2] - 1 + 8) % 8;
				}
				right[3] = (right[3] + 1) % 8;
				left[3] = (left[3] + 1) % 8;
			}
		}
	}
	int sum = 0;
	if (wheel[0][(left[0] + 2) % 8] == '1') {
		sum += 1;
	}
	if (wheel[1][(left[1] + 2) % 8] == '1') {
		sum += 2;
	}
	if (wheel[2][(left[2] + 2) % 8] == '1') {
		sum += 4;
	}
	if (wheel[3][(left[3] + 2) % 8] == '1') {
		sum += 8;
	}
	cout << sum << endl;
	return 0;
}
728x90
728x90

단계별로 풀어보기 문자열의 3단계 문제

 

10809번: 알파벳 찾기

각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다.

www.acmicpc.net

c++의 <string>을 포함하고 <string>의 편리한 함수를 사용하면 쉽게 풀 수 있다.

find 함수의 사용법은 다음과 같다.

string s1("Welcome");
cout << s1.find('o') << endl; // 4 출력 (처음부터 찾음)
cout << s1.find('o', 6) << endl; // 9 출력. (인덱스 6부터 'o'를 찾음)
if (s1.find("el", 3) == string::npos)
	cout << "el은 없습니다" << endl;

find 함수는 찾고자 하는 문자 또는 문자열이 없으면 string::npos를 반환한다.

 

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


int main() {
	string s;
	cin >> s;
	int alphabet[26];
	for (int i = 0; i < 26; i++) {
		alphabet[i] = -1;
	}
	alphabet[0] = s.find('a');
	alphabet[1] = s.find('b');
	alphabet[2] = s.find('c');
	alphabet[3] = s.find('d');
	alphabet[4] = s.find('e');
	alphabet[5] = s.find('f');
	alphabet[6] = s.find('g');
	alphabet[7] = s.find('h');
	alphabet[8] = s.find('i');
	alphabet[9] = s.find('j');
	alphabet[10] = s.find('k');
	alphabet[11] = s.find('l');
	alphabet[12] = s.find('m');
	alphabet[13] = s.find('n');
	alphabet[14] = s.find('o');
	alphabet[15] = s.find('p');
	alphabet[16] = s.find('q');
	alphabet[17] = s.find('r');
	alphabet[18] = s.find('s');
	alphabet[19] = s.find('t');
	alphabet[20] = s.find('u');
	alphabet[21] = s.find('v');
	alphabet[22] = s.find('w');
	alphabet[23] = s.find('x');
	alphabet[24] = s.find('y');
	alphabet[25] = s.find('z');
	for (int i = 0; i < 26; i++) {
		cout << alphabet[i] << " ";
	}
	return 0;
}
728x90
728x90

단계별로 풀어보기 백트래킹의 8단계 문제이자 삼성 SW 역량 테스트 기출 문제인 14889번 문제

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

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

int n;
bool* visited;
int* startMembers;
int* linkMembers;
int** arr;
vector<int> difference;

int ability(int* members) {
	int sum = 0;
	for (int i = 0; i < n / 2; i++) {
		for (int j = 0; j < n / 2; j++) {
			if (j != i) {
				sum += arr[members[i]][members[j]];
			}
		}
	}
	//cout << "sum은 " << sum << " ";
	return sum;
}
void divideTeam(int num) {
	if (num == n / 2) {
		int index = 0;
		for (int i = 0; i < n; i++) {
			bool flag = true;
			for (int j = 0; j < n / 2; j++) {
				if (startMembers[j] == i) {
					flag = false;
				}
			}
			if (flag) {
				linkMembers[index] = i;
				index++;
				if (index == n / 2) break;
			}
		}
		difference.push_back(abs(ability(startMembers) - ability(linkMembers)));
		return;
	}
	for (int i = 0; i < n; i++) {
		if (num > 0) {
			if (startMembers[num - 1] < i) {
				if (!visited[i]) {
					startMembers[num] = i;
					visited[i] = true;
					divideTeam(num + 1);
					visited[i] = false;
				}
			}
		}
		else {
			if (!visited[i]) {
				startMembers[num] = i;
				visited[i] = true;
				divideTeam(num + 1);
				visited[i] = false;
			}

		}
	}
}


int main() {
	cin >> n;
	arr = new int*[n];
	visited = new bool[n];
	for (int i = 0; i < n; i++) {
		visited[i] = false;
	}
	for (int i = 0; i < n; i++) {
		arr[i] = new int[n];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	startMembers = new int[n / 2];
	linkMembers = new int[n / 2];
	divideTeam(0);
	int minDifference = difference[0];
	for (int i = 1; i < difference.size(); i++) {
		if (difference[i] < minDifference)
			minDifference = difference[i];
	}
	cout << minDifference << endl;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 14891번 톱니바퀴  (0) 2020.01.27
[백준] 10809번 알파벳 찾기  (0) 2020.01.26
[백준] 14888번 연산자 끼워넣기  (0) 2020.01.25
[백준] 1152번 단어의 개수  (0) 2020.01.25
[백준] 2580번 스도쿠  (0) 2020.01.25
728x90

삼성 SW 역량 테스트 기출 문제이자 단계별로 풀어보기 백트래킹의 7단계 문제

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

www.acmicpc.net

처음에 분명히 맞게 풀었는데 컴파일 에러가 나는 것이었다. 원인은 min과 max라는 변수 이름 때문이었다.

따라서 min을 minn으로, max를 maxx로 바꿔줬더니 성공

#include <iostream>
using namespace std;

int n;
int* numbers;
int maxx = -1000000000;
int minn = 1000000000;

void select(char* oper, int num, int plusRemain, int minusRemain, int multiplyRemain, int divideRemain) {
	if (num == n - 1) {
		int result = numbers[0];
		for (int i = 0; i < n - 1; i++) {
			switch (oper[i]) {
			case '+':
				result += numbers[i + 1]; break;
			case '-':
				result -= numbers[i + 1]; break;
			case '*':
				result *= numbers[i + 1]; break;
			case '/':
				result /= numbers[i + 1]; break;
			}
		}
		if (result > maxx) maxx = result;
		if (result < minn) minn = result;
		return;
	}
	if (plusRemain > 0) {
		oper[num] = '+';
		select(oper, num + 1, plusRemain - 1, minusRemain, multiplyRemain, divideRemain);
	}
	if (minusRemain > 0) {
		oper[num] = '-';
		select(oper, num + 1, plusRemain, minusRemain - 1, multiplyRemain, divideRemain);
	}
	if (multiplyRemain > 0) {
		oper[num] = '*';
		select(oper, num + 1, plusRemain, minusRemain, multiplyRemain - 1, divideRemain);
	}
	if (divideRemain > 0) {
		oper[num] = '/';
		select(oper, num + 1, plusRemain, minusRemain, multiplyRemain, divideRemain - 1);
	}
}

int main() {
	cin >> n;
	numbers = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	int plus, minus, multiply, divide;
	cin >> plus >> minus >> multiply >> divide;
	char* oper = new char[n - 1];
	select(oper, 0, plus, minus, multiply, divide);	
	cout << maxx << endl;
	cout << minn << endl;
	return 0;
}
728x90
728x90
 

1152번: 단어의 개수

첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다.

www.acmicpc.net

자바의 StringTokenizer를 이용해서 손쉽게 풀 수 있었다. C++로도 한 번 더 풀어봐야겠다.

import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        int count = 0;
        while (st.hasMoreTokens()) {
            st.nextToken();
            count ++;
        }
        System.out.println(count);
    }
}
728x90
728x90
 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3

www.acmicpc.net

입력을 받을 때 0인 것의 위치를 emptyLocation이라는 벡터에 집어넣는다.

그리고 1부터 9까지의 수로 emptyLocation.size() 만큼의 중복순열을 구한다.

check 함수는 숫자를 배치하려고 하는 위치에 그 값을 집어넣는 것이 바람직한지 체크해서 true나 false를 리턴해주는 함수이다.

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

int sudoku[9][9];
bool flag = false;
bool check(int row, int col, int value) {
	for (int i = 0; i < 9; i++) { //row번째 가로줄, col번째 세로줄에 value와 같은 값이 있는지 체크
		if (sudoku[row][i] == value || sudoku[i][col] == value)
			return false;
	}
	//(row, col)이 몇 번째 사각형에 속하는지 알아보고 그 사각형에 value와 같은 값이 있는지 체크
	int recRow = row / 3;
	int recCol = col / 3;
	for (int i = recRow * 3; i < recRow * 3 + 3; i++) {
		for (int j = recCol * 3; j < recCol * 3 + 3; j++) {
			if (sudoku[i][j] == value)
				return false;
		}
	}
	return true;
}

void select(int* result, vector<pair<int, int>> emptyLocation, int num) {
	if (num == emptyLocation.size()) {

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << sudoku[i][j] << " ";
			}
			cout << endl;
		}
		flag = true;
		return;
	}

	for (int i = 1; i <= 9; i++) {
		if (check(emptyLocation[num].first, emptyLocation[num].second, i) && !flag) {
			result[num] = i;
			sudoku[emptyLocation[num].first][emptyLocation[num].second] = i;
			select(result, emptyLocation, num + 1);
			sudoku[emptyLocation[num].first][emptyLocation[num].second] = 0;
		}
		if (flag) {
			return;
		}
	}
}

int main() {
	vector<pair<int, int>> emptyLocation;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> sudoku[i][j];
			if (sudoku[i][j] == 0) {
				emptyLocation.push_back(make_pair(i, j));
			}
		}
	}
	int count = emptyLocation.size();
	int* result = new int[count];
	select(result, emptyLocation, 0);

	return 0;
}
728x90
728x90

단계별로 풀어보기 수학 1의 7단계 문제

 

2775번: 부녀회장이 될테야

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)

www.acmicpc.net

배열을 하나 만들어놓고 차곡차곡 더해서 저장하면 된다.

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

int main() {
	int a;
	cin >> a;
	int** input = new int*[a];
	for (int i = 0; i < a; i++) {
		input[i] = new int[2];
	}
	int maxFloor = 0;
	int maxNumber = 1;
	for (int i = 0; i < a; i++) {
		int floor, number;
		cin >> floor >> number;
		if (floor > maxFloor) maxFloor = floor;
		if (number > maxNumber) maxNumber = number;
		input[i][0] = floor;
		input[i][1] = number;
	}
	int** apartment = new int*[maxFloor + 1];
	for (int i = 0; i < maxFloor + 1; i++) {
		apartment[i] = new int[maxNumber];
	}
	for (int i = 0; i <= maxFloor; i++) {
		apartment[0][i] = i + 1; //0층 i호를 i + 1로 초기화
	}
	for (int i = 1; i < maxFloor + 1; i++) { //1층부터 k층까지
		int sum = 0;
		for (int j = 0; j < maxNumber; j++) { //1호부터 n호까지
			sum += apartment[i - 1][j];
			apartment[i][j] = sum;
		}
	}
	for (int i = 0; i < a; i++) {
		cout << apartment[input[i][0]][input[i][1] - 1] << endl;
	}

	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 1152번 단어의 개수  (0) 2020.01.25
[백준] 2580번 스도쿠  (0) 2020.01.25
[백준] 2156번 포도주 시식  (0) 2020.01.24
[백준] 2579번 계단 오르기  (0) 2020.01.24
[백준] 2446번 별 찍기 - 9  (0) 2020.01.22

+ Recent posts