728x90

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

 

5086번: 배수와 약수

문제 4 × 3 = 12이다. 이 식을 통해 다음과 같은 사실을 알 수 있다. 3은 12의 약수이고, 12는 3의 배수이다. 4도 12의 약수이고, 12는 4의 배수이다. 두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오. 첫 번째 숫자가 두 번째 숫자의 약수이다. 첫 번째 숫자가 두 번째 숫자의 배수이다. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다. 입력 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스

www.acmicpc.net

#include <iostream>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	while (true) {
		int a, b;
		cin >> a >> b;
		if (a == 0 && b == 0) {
			break;
		}
		if (a % b == 0) {
			cout << "multiple\n";
		}
		else if (b % a == 0) {
			cout << "factor\n";
		}
		else {
			cout << "neither\n";
		}
	}
	return 0;
}
728x90

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

[백준] 2589번 보물섬  (0) 2020.04.07
[백준] 2630번 색종이 만들기  (0) 2020.03.30
[백준] 10996번 별 찍기 - 21  (0) 2020.03.30
[백준] 10039번 평균 점수  (0) 2020.03.29
[백준] 14681번 사분면 고르기  (0) 2020.03.29
728x90

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

 

10996번: 별 찍기 - 21

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

www.acmicpc.net

#include <iostream>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	if (n == 1) {
		cout << '*';
	}
	else {
		for (int i = 0; i < 2 * n; i++) {
			for (int j = 0; j < n; j++) {
				if (i % 2 == 0) {
					if (j % 2 == 0) {
						cout << '*';
					}
					else {
						cout << " ";
					}
				}
				else {
					if (j % 2 == 0) {
						cout << " ";
					}
					else {
						cout << '*';
					}
				}
			}
			cout << '\n';
		}
	}
	return 0;
}
728x90

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

[백준] 2630번 색종이 만들기  (0) 2020.03.30
[백준] 5086번 배수와 약수  (0) 2020.03.30
[백준] 10039번 평균 점수  (0) 2020.03.29
[백준] 14681번 사분면 고르기  (0) 2020.03.29
[백준] 13458번 시험 감독  (0) 2020.03.25
728x90

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

 

10039번: 평균 점수

문제 상현이가 가르치는 아이폰 앱 개발 수업의 수강생은 원섭, 세희, 상근, 숭, 강수이다. 어제 이 수업의 기말고사가 있었고, 상현이는 지금 학생들의 기말고사 시험지를 채점하고 있다. 기말고사 점수가 40점 이상인 학생들은 그 점수 그대로 자신의 성적이 된다. 하지만, 40점 미만인 학생들은 보충학습을 듣는 조건을 수락하면 40점을 받게 된다. 보충학습은 거부할 수 없기 때문에, 40점 미만인 학생들은 항상 40점을 받게 된다. 학생 5명의 점수가 주어

www.acmicpc.net

#include <iostream>
using namespace std;

int main() {
	int arr[5];
	for (int i = 0; i < 5; i++) {
		cin >> arr[i];
		if (arr[i] < 40)
			arr[i] = 40;
	}
	int sum = 0;
	for (int i = 0; i < 5; i++) {
		sum += arr[i];
	}
	cout << sum / 5;
	return 0;
}
728x90

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

[백준] 5086번 배수와 약수  (0) 2020.03.30
[백준] 10996번 별 찍기 - 21  (0) 2020.03.30
[백준] 14681번 사분면 고르기  (0) 2020.03.29
[백준] 13458번 시험 감독  (0) 2020.03.25
[백준] 2010번 플러그  (0) 2020.03.23
728x90

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

 

14681번: 사분면 고르기

문제 흔한 수학 문제 중 하나는 주어진 점이 어느 사분면에 속하는지 알아내는 것이다. 사분면은 아래 그림처럼 1부터 4까지 번호를 갖는다. "Quadrant n"은 "제n사분면"이라는 뜻이다. 예를 들어, 좌표가 (12, 5)인 점 A는 x좌표와 y좌표가 모두 양수이므로 제1사분면에 속한다. 점 B는 x좌표가 음수이고 y좌표가 양수이므로 제2사분면에 속한다. 점의 좌표를 입력받아 그 점이 어느 사분면에 속하는지 알아내는 프로그램을 작성하시오. 단, x좌표

www.acmicpc.net

#include <iostream>
using namespace std;

int main() {
	int x, y; 
	cin >> x >> y;
	if (x > 0 && y > 0) {
		cout << 1;
	}
	else if (x > 0 && y < 0) {
		cout << 4;
	}
	else if (x < 0 && y > 0) {
		cout << 2;
	}
	else {
		cout << 3;
	}
	return 0;
}
728x90

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

[백준] 10996번 별 찍기 - 21  (0) 2020.03.30
[백준] 10039번 평균 점수  (0) 2020.03.29
[백준] 13458번 시험 감독  (0) 2020.03.25
[백준] 2010번 플러그  (0) 2020.03.23
[백준] 1476번 날짜 계산  (0) 2020.03.23
728x90

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

 

13458번: 시험 감독

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

www.acmicpc.net

Ai - b (각 시험장에 있는 응시자의 수 - 총감독관이 한 시험장에서 감시할 수 있는 응시자의 수) 이렇게 뺄셈할 때 주의할 점이 있다. 총감독관이 한 시험장에서 감시할 수 있는 응시자의 수가 각 시험장의 응시자 수보다 클 수 있다. 따라서 이렇게 빼면 음수가 될 수도 있다.

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

int main() {
	long long n;
	cin >> n;
	vector<int> numOfPeople(n);
	for (int i = 0; i < n; i++) {
		cin >> numOfPeople[i];
	}
	long long b, c;
	cin >> b >> c;
	long long total = n;
	for (int i = 0; i < n; i++) {
		if ((numOfPeople[i] - b) % c == 0) {
			if (numOfPeople[i] - b > 0)
				total += (numOfPeople[i] - b) / c;
		}
		else {
			if (numOfPeople[i] - b > 0)
				total += (numOfPeople[i] - b) / c + 1;
		}
	}
	cout << total;
	return 0;
}
728x90

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

[백준] 10039번 평균 점수  (0) 2020.03.29
[백준] 14681번 사분면 고르기  (0) 2020.03.29
[백준] 2010번 플러그  (0) 2020.03.23
[백준] 1476번 날짜 계산  (0) 2020.03.23
[백준] 1357번 뒤집힌 덧셈  (0) 2020.03.23
728x90

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

 

2010번: 플러그

문제 선영이의 집에는 콘센트를 꽂을 수 있는 플러그가 하나밖에 없다. 선영이는 많은 컴퓨터를 가지고 있는데, 컴퓨터의 전원 문제는 어떻게 해결하는 것일까? 하나의 플러그가 있고, N개의 멀티탭이 있다. 각 멀티탭은 몇 개의 플러그로 이루어져 있다고 한다. 최대 몇 대의 컴퓨터를 전원에 연결할 수 있을까? 입력 첫째 줄에 멀티탭의 개수 N이 주어진다. (1<=N<=500,000) 이어서 둘째 줄부터 N개의 줄에 걸쳐 각 멀티탭이 몇 개의 플러그를 꽂을 수

www.acmicpc.net

멀티탭도 일단 어떤 콘센트에 꽂아야 한다. 따라서 멀티탭의 개수만큼 빼줘야 한다. 그리고 선영이의 집에는 콘센트가 한 개 있기 때문에 이것도 더해줘야 한다.

즉, 모든 콘센트의 개수 + 1 - 멀티탭의 개수이다.

이 문제에서는 콘센트라는 단어와 플러그라는 단어를 반대로 쓴 것 같다.

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

int main() {
	int n;
	cin >> n;
	vector<int> multiTab(n);
	int total = 0;
	for (int i = 0; i < n; i++) {
		cin >> multiTab[i];
		total += multiTab[i];
	}
	cout << total + 1 - n;
	return 0;
}

 

728x90

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

[백준] 14681번 사분면 고르기  (0) 2020.03.29
[백준] 13458번 시험 감독  (0) 2020.03.25
[백준] 1476번 날짜 계산  (0) 2020.03.23
[백준] 1357번 뒤집힌 덧셈  (0) 2020.03.23
[백준] 1074번 Z  (0) 2020.03.23
728x90

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

 

1476번: 날짜 계산

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1

www.acmicpc.net

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

int main() {
	int e, s, m;
	cin >> e >> s >> m;
	int a, b, c;
	a = b = c = 1;
	int cnt = 1;
	while (true) {
		if (e == a && s == b && m == c) {
			break;
		}
		a = (a + 1) % 16;
		b = (b + 1) % 29;
		c = (c + 1) % 20;
		if (a == 0)
			a = 1;
		if (b == 0)
			b = 1;
		if (c == 0)
			c = 1;
		cnt++;
	}
	cout << cnt;
	return 0;
}
728x90

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

[백준] 13458번 시험 감독  (0) 2020.03.25
[백준] 2010번 플러그  (0) 2020.03.23
[백준] 1357번 뒤집힌 덧셈  (0) 2020.03.23
[백준] 1074번 Z  (0) 2020.03.23
[백준] 11066번 파일 합치기  (0) 2020.03.20
728x90

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

 

1357번: 뒤집힌 덧셈

어떤 수 X가 주어졌을 때, X의 모든 자리수가 역순이 된 수를 얻을 수 있다. Rev(X)를 X의 모든 자리수를 역순으로 만드는 함수라고 하자. 예를 들어, X=123일 때, Rev(X) = 321이다. 그리고, X=100일 때, Rev(X) = 1이다. 두 양의 정수 X와 Y가 주어졌을 때, Rev(Rev(X) + Rev(Y))를 구하는 프로그램을 작성하시오

www.acmicpc.net

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

int main() {
	string x, y;
	cin >> x >> y;
	string a = "";
	string b = "";
	for (int i = x.size() - 1; i >= 0; i--) {
		a += x[i];
	}
	for (int i = y.size() - 1; i >= 0; i--) {
		b += y[i];
	}
	int temp = stoi(a) + stoi(b);
	string result = "";
	while (true) {
		if (temp / 10 == 0) {
			result += (temp % 10 + '0');
			break;
		}
		result += (temp % 10 + '0');
		temp /= 10;
	}
	cout << stoi(result);
	return 0;
}
728x90

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

[백준] 2010번 플러그  (0) 2020.03.23
[백준] 1476번 날짜 계산  (0) 2020.03.23
[백준] 1074번 Z  (0) 2020.03.23
[백준] 11066번 파일 합치기  (0) 2020.03.20
[백준] 9325번 얼마?  (0) 2020.03.20
728x90

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

 

1074번: Z

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r,

www.acmicpc.net

문제에서 주어준대로 재귀로 풀면 되기 때문에 아주 쉽게 풀 수 있었다.

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

int n, r, c;
int cnt = 0;
int result;
bool found = false;

void visit(int rowStart, int rowEnd, int colStart, int colEnd) {
	if (found)
		return;
	if (rowEnd - rowStart == 1) {
		if (++cnt && rowStart == r && colStart == c) {
			result = cnt;
			found = true;
			return;
		}
		else if (++cnt && rowStart == r && colEnd == c) {
			result = cnt;
			found = true;
			return;
		}
		else if (++cnt && rowEnd == r && colStart == c) {
			result = cnt;
			found = true;
			return;
		}
		else if (++cnt && rowEnd == r && colEnd == c) {
			result = cnt;
			found = true;
			return;
		}
		else {
			return;
		}
	}
	visit(rowStart, rowStart + (rowEnd + 1 - rowStart) / 2 - 1, colStart, colStart + (colEnd + 1 - colStart) / 2 - 1);
	visit(rowStart, rowStart + (rowEnd + 1 - rowStart) / 2 - 1, colStart + (colEnd + 1 - colStart) / 2, colEnd);
	visit(rowStart + (rowEnd + 1 - rowStart) / 2, rowEnd, colStart, colStart + (colEnd + 1 - colStart) / 2 - 1);
	visit(rowStart + (rowEnd + 1 - rowStart) / 2, rowEnd, colStart + (colEnd + 1 - colStart) / 2, colEnd);
}

int main() {
	cin >> n >> r >> c;
	n = pow(2, n);
	visit(0, n - 1, 0, n - 1);
	cout << result - 1;
	return 0;
}
728x90

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

[백준] 1476번 날짜 계산  (0) 2020.03.23
[백준] 1357번 뒤집힌 덧셈  (0) 2020.03.23
[백준] 11066번 파일 합치기  (0) 2020.03.20
[백준] 9325번 얼마?  (0) 2020.03.20
[백준] 4539번 반올림  (0) 2020.03.20
728x90

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

11066번: 파일 합치기

문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을

www.acmicpc.net

정말 역대급 어려웠던 문제였다고 생각한다. 정답률은 50%가 넘는데 그거는 예제입력조차 정답이 나오지 않아서 사람들이 제출 시도 자체를 안 해서 그러는 것 같다. 솔직히 이 문제는 예제입력에서 정답이 나왔을 때 제출하면 거의 정답일 것 같다.

 

이 문제에서 주의할 것은 이 파일은 소설의 챕터이기 때문에 순서를 마음대로 바꾸면 안 된다. 무조건 입력으로 주어진 순서에서 인접한 파일끼리만 합칠 수 있다.

 

일단 코드부터 보자면

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

int main() {
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int n;
		cin >> n;
		vector<int> v(n + 1);
		vector<int> sum(n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> v[i];
			if (i == 0) {
				sum[i] = v[i];
			}
			else {
				sum[i] = sum[i - 1] + v[i];
			}
		}
		vector<vector<int>> dp(n + 1, vector<int>(n + 1));
		for (int gap = 1; gap < n; gap++) {
			for (int start = 1; start + gap <= n; start++) {
				int end = start + gap;
				dp[start][end] = INT_MAX;
				for (int mid = start; mid < end; mid++) {
					if (dp[start][end] > dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start - 1]) {
						dp[start][end] = dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start - 1];
					}
				}
			}
		}
		cout << dp[1][n] << '\n';
	}
	return 0;
}

테스트 케이스가 여러개라 돌리는 가장 바깥 for문을 제외하고 3중 for문이 핵심이다.

이차원 배열 dp[i][j]에는 i번째 챕터부터 j번째 챕터까지 합치는데에 드는 최소비용을 저장한다.

우리가 구하고자 하는 것은 "하나의 파일"로 합칠 때 필요한 최소비용이므로 dp[1][n]을 구하면 된다.

 

3중 for문 중 가장 바깥 for문은 gap을 1씩 늘려가면서 돌아가는데 dp[i][j]에서 i와 j의 차이(간격)를 정해주는 for문이다.

만약 gap이 1이면 챕터 1과 2를 합친다던지 챕터 2와 3을 합치는 것과 같이 두 개의 연속된 챕터를 합치는 것이다.

gap이 2라면 챕터 1부터 챕터3까지 합친다던지 3개의 연속된 챕터를 합치는 것이다.

 

3중 for문 중 두 번째 for문(중간 for문)은 start를 1씩 늘려가면서 돌아가는데 dp[i][j]에서 i를 정해주는 for문이다.

즉, start는 "몇 번째 챕터부터" 더할지를 정하는 것이다.

gap이 3이고 start가 2라면 dp[2][2+3] 즉 dp[2][5]를 구하는 것이다.

따라서 end라는 변수를 만들어 start+gap을 end라는 변수에 저장해주었다. 윗줄 예시에서 end는 2+3=5이다.

 

제일 안쪽 for문은 mid를 1씩 늘려가면서 돌아간다. 파일을 합칠 때에는 두 개의 파일을 합쳐야 한다.

따라서 start~mid까지의 챕터와 mid+1~end 챕터를 더하게 될 텐데 그 두 부분으로 분리되는 부분이 바로 mid이다.

예를 들어 start가 1이고 gap이 4라서 dp[1][5]를 구해야 한다면 챕터1부터 챕터5까지를 합치는 최소 비용을 구하는 것인데

챕터1/챕터2~5 이렇게 두 부분을 합칠 수도 있고 (이 경우 mid는 1)

챕터 1~2/챕터3~5 이렇게 두 부분을 합칠 수도 있고 (이 경우 mid는 2)

챕터 1~3/챕터4~5 이렇게 두 부분을 합칠 수도 있고 (이 경우 mid는 3)

챕터 1~4/챕터5 이렇게 두 부분을 합칠 수도 있다. (이 경우 mid는 4)

mid의 역할이 바로 이렇다.

for문의 조건 부분이 mid <= end가 아니라 mid < end인 이유는 최소한 두 부분으로는 나눠져야 하기 때문이다.

만약 end와 mid가 같다면

챕터 1~5/없음 (mid가 5라면 즉, mid가 end와 같다면)

이렇게 챕터 1~5를 제외하면 나머지 부분은 없기 때문에 무조건 mid는 end보다 작아야 한다.

 

그리고 sum[i]에는 첫 번째 챕터부터 i번째 챕터까지의 합이 저장되어 있다.

따라서 sum[end] - sum[start - 1]은

(챕터1~챕터end까지의 합) - (챕터1~챕터 start-1까지의 합)이기 때문에

챕터start~챕터end까지의 합을 뜻한다.

 

 

 

728x90

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

[백준] 1357번 뒤집힌 덧셈  (0) 2020.03.23
[백준] 1074번 Z  (0) 2020.03.23
[백준] 9325번 얼마?  (0) 2020.03.20
[백준] 4539번 반올림  (0) 2020.03.20
[백준] 1965번 상자넣기  (0) 2020.03.17

+ Recent posts