728x90

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

 

5338번: 마이크로소프트 로고

문제 마이크로소프트 로고를 예제 출력처럼 출력하는 프로그램을 작성하시오. 출력 마이크로소프트 로고를 예제 출력처럼 출력한다. 예제 입력 1 복사 예제 출력 1 복사 _.-;;-._ '-..-'| || | '-..-'|_.-;;-._| '-..-'| || | '-..-'|_.-''-._|...

www.acmicpc.net

#include <iostream>
using namespace std;

int main() {
	cout << "       _.-;;-._" << '\n';
	cout << "'-..-'|   ||   |" << '\n';
	cout << "'-..-'|_.-;;-._|" << '\n';
	cout << "'-..-'|   ||   |" << '\n';
	cout << "'-..-'|_.-''-._|" << '\n';
	return 0;
}
728x90

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

[백준] 1937번 욕심쟁이 판다  (0) 2020.03.14
[백준] 3036번 링  (0) 2020.03.13
[백준] 1699번 제곱수의 합  (0) 2020.03.13
[백준] 2294번 동전 2  (0) 2020.03.12
[백준] 1520번 내리막 길  (0) 2020.03.11
728x90

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

 

1699번: 제곱수의 합

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는

www.acmicpc.net

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

int main() {
	int n;
	cin >> n;
	vector<int> dp(n + 1, 1000000);
	for (int i = 1; i <= sqrt(n); i++) {
		dp[i * i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for(int j = 1; j * j < i; j++) {
			dp[i] = min(dp[i], 1 + dp[i - j * j]);
		}
	}
	/*for (int i = 1; i <= n; i++) {
		cout << setw(3) << i;
	}
	cout << endl;
	for (int i = 1; i <= n; i++) {
		cout << setw(3) << dp[i];
	}
	cout << endl;*/
	cout << dp[n];
	return 0;
}
728x90

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

[백준] 3036번 링  (0) 2020.03.13
[백준] 5338번 마이크로소프트 로고  (0) 2020.03.13
[백준] 2294번 동전 2  (0) 2020.03.12
[백준] 1520번 내리막 길  (0) 2020.03.11
[백준] 2293번 동전 1  (0) 2020.03.08
728x90

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

 

2294번: 동전 2

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

www.acmicpc.net

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> coin(n);
	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}
	sort(coin.begin(), coin.end());
	vector<vector<int>> dp(n, vector<int>(k + 1, 100001));
	for (int i = 1; i <= k; i++) {
		if (i % coin[0] == 0) {
			dp[0][i] = i / coin[0];
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j < coin[i]) {
				dp[i][j] = dp[i - 1][j];
			}
			else if (j == coin[i]) {
				dp[i][j] = 1;
			}
			else {
				dp[i][j] = min(dp[i - 1][j], dp[i][j - coin[i]] + 1);
				
			}
		}
	}
	/*cout << "   ";
	for (int i = 0; i <= k; i++) {
		cout << setw(3) << i;
	}
	cout << endl;
	for (int i = 0; i < n; i++) {
		cout << setw(3) << coin[i];
		for (int j = 0; j <= k; j++) {
			if(dp[i][j] != 100001)
				cout << setw(3) << dp[i][j];
			else 
				cout << setw(3) << 0;
		}
		cout << endl;
	}*/
	if (dp[n - 1][k] != 100001) cout << dp[n - 1][k];
	else cout << -1;
	return 0;
}

 

728x90

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

[백준] 5338번 마이크로소프트 로고  (0) 2020.03.13
[백준] 1699번 제곱수의 합  (0) 2020.03.13
[백준] 1520번 내리막 길  (0) 2020.03.11
[백준] 2293번 동전 1  (0) 2020.03.08
[백준] 1057번 토너먼트  (0) 2020.03.07
728x90

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

 

1520번: 내리막 길

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

www.acmicpc.net

dfs+dp로 풀 수 있었다. 리턴값이 있는 재귀함수에 더 익숙해져야겠다.

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

int n, m;
vector<vector<int>> v;
vector<vector<int>> dp;

int dfs(int row, int col) {
	if (dp[row][col] == -1) {
		dp[row][col] = 0;
		if (row + 1 < n && v[row][col] > v[row + 1][col]) {
			dp[row][col] += dfs(row + 1, col);
		}
		if (col + 1 < m && v[row][col] > v[row][col + 1]) {
			dp[row][col] += dfs(row, col + 1);
		}
		if (row - 1 >= 0 && v[row][col] > v[row - 1][col]) {
			dp[row][col] += dfs(row - 1, col);
		}
		if (col - 1 >= 0 && v[row][col] > v[row][col - 1]) {
			dp[row][col] += dfs(row, col - 1);
		}
	}
	return dp[row][col];
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	v = vector<vector<int>>(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> v[i][j];
		}
	}
	dp = vector<vector<int>>(n, vector<int>(m, -1));
	dp[n - 1][m - 1] = 1;
	cout << dfs(0, 0);
	return 0;
}
728x90

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

[백준] 1699번 제곱수의 합  (0) 2020.03.13
[백준] 2294번 동전 2  (0) 2020.03.12
[백준] 2293번 동전 1  (0) 2020.03.08
[백준] 1057번 토너먼트  (0) 2020.03.07
[백준] 2309번 일곱 난쟁이  (0) 2020.03.07
728x90

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

 

2293번: 동전 1

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

www.acmicpc.net

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> coin(n);
	coin = vector<int>(n);
	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}
	vector<int> dp(k + 1, 0);
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j >= coin[i]) {
				dp[j] = dp[j] + dp[j - coin[i]];
			}
		}
	}
	cout << dp[k];
	return 0;
}
728x90

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

[백준] 2294번 동전 2  (0) 2020.03.12
[백준] 1520번 내리막 길  (0) 2020.03.11
[백준] 1057번 토너먼트  (0) 2020.03.07
[백준] 2309번 일곱 난쟁이  (0) 2020.03.07
[백준] 3053번 택시 기하학  (0) 2020.03.07
728x90

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

 

1057번: 토너먼트

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음

www.acmicpc.net

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

vector<int> arr[18];

int main() {
	int n, a, b;
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) {
		arr[0].push_back(i);
	}
	int row = 0;
	int result;
	bool flag = false;
	while (true) {
		for (int i = 0; i < arr[row].size(); i += 2) {
			if (i + 1 >= arr[row].size()) {
				arr[row + 1].push_back(arr[row][i]);
			}
			else if ((arr[row][i] == a || arr[row][i] == b) && (arr[row][i + 1] == a || arr[row][i + 1] == b)) {
				result = row + 1;
				flag = true;
				break;
			}
			else {
				if (arr[row][i] == a || arr[row][i] == b) {
					arr[row + 1].push_back(arr[row][i]);
				}
				else if (arr[row][i + 1] == a || arr[row][i + 1] == b) {
					arr[row + 1].push_back(arr[row][i + 1]);
				}
				else {
					arr[row + 1].push_back(arr[row][i]);
				}
			}
		}
		if (flag) break;
		row++;
	}
	cout << result;
	return 0;
}
728x90

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

[백준] 1520번 내리막 길  (0) 2020.03.11
[백준] 2293번 동전 1  (0) 2020.03.08
[백준] 2309번 일곱 난쟁이  (0) 2020.03.07
[백준] 3053번 택시 기하학  (0) 2020.03.07
[백준] 1002번 터렛  (0) 2020.03.07
728x90

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

 

2309번: 일곱 난쟁이

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

www.acmicpc.net

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

int arr[9];
int flag = false;

void combination(int num, vector<int> result, vector<bool> visited) {
	if (flag) return;
	if (num == 7) {
		int total = 0;
		for (int i = 0; i < 7; i++) {
			total += result[i];
		}
		if (total == 100) {
			flag = true;
			for (int i = 0; i < 7; i++) {
				cout << result[i] << endl;
			}
		}
		return;
	}
	for (int i = 0; i < 9; i++) {
		if (num == 0) {
			if (!visited[i]) {
				visited[i] = true;
				result[num] = arr[i];
				combination(num + 1, result, visited);
				visited[i] = false;
			}
		}
		else {
			if (arr[i] > result[num - 1]) {
				if (!visited[i]) {
					visited[i] = true;
					result[num] = arr[i];
					combination(num + 1, result, visited);
					visited[i] = false;
				}
			}
		}
	}
}

int main() {
	for (int i = 0; i < 9; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + 9);
	vector<int> result(7);
	vector<bool> visited(9);
	combination(0, result, visited);
	return 0;
}
728x90

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

[백준] 2293번 동전 1  (0) 2020.03.08
[백준] 1057번 토너먼트  (0) 2020.03.07
[백준] 3053번 택시 기하학  (0) 2020.03.07
[백준] 1002번 터렛  (0) 2020.03.07
[백준] 5543번 상근날드  (0) 2020.03.07
728x90

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

 

3053번: 택시 기하학

문제 19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다. 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다. D(T1,T2) = |x1-x2| + |y1-y2| 두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다. 따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다. 원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합

www.acmicpc.net

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


int main() {
	int r;
	cin >> r;
	cout << fixed << showpoint << setprecision(6) << r * r * 3.1415926535897932 << endl;
	cout << (double)(r * r * 2) << endl;
	system("pause");
	return 0;
}
728x90

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

[백준] 1057번 토너먼트  (0) 2020.03.07
[백준] 2309번 일곱 난쟁이  (0) 2020.03.07
[백준] 1002번 터렛  (0) 2020.03.07
[백준] 5543번 상근날드  (0) 2020.03.07
[백준] 2206번 벽 부수고 이동하기  (0) 2020.03.03
728x90

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

 

1002번: 터렛

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

www.acmicpc.net

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


int main() {
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int x1, y1, r1, x2, y2, r2;
		cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
		double distance = pow(x1 - x2, 2) + pow(y1 - y2, 2);
		if (x1 == x2 && y1 == y2 && r1 == r2/*같은 원*/)
			cout << -1 << '\n';
		else if ((x1 == x2 && y1 == y2 && r1 != r2)/*동심원*/ || distance < pow(r1 - r2, 2)/*외부*/ || pow(r1 + r2, 2) < distance/*내부*/)
			cout << 0 << '\n';
		else if (pow(r1 + r2, 2) == distance/*외접*/ || pow(r1 - r2, 2) == distance/*내접*/)
			cout << 1 << '\n';
		else
			cout << 2 << '\n';
	}
	return 0;
}
728x90

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

[백준] 2309번 일곱 난쟁이  (0) 2020.03.07
[백준] 3053번 택시 기하학  (0) 2020.03.07
[백준] 5543번 상근날드  (0) 2020.03.07
[백준] 2206번 벽 부수고 이동하기  (0) 2020.03.03
[백준] 11816번 8진수, 10진수, 16진수  (0) 2020.03.03
728x90

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

 

5543번: 상근날드

문제 상근날드에서 가장 잘 팔리는 메뉴는 세트 메뉴이다. 주문할 때, 자신이 원하는 햄버거와 음료를 하나씩 골라, 세트로 구매하면, 가격의 합계에서 50원을 뺀 가격이 세트 메뉴의 가격이 된다. 햄버거는 총 3종류 상덕버거, 중덕버거, 하덕버거가 있고, 음료는 콜라와 사이다 두 종류가 있다. 햄버거와 음료의 가격이 주어졌을 때, 가장 싼 세트 메뉴의 가격을 출력하는 프로그램을 작성하시오. 입력 입력은 총 다섯 줄이다. 첫째 줄에는 상덕버거, 둘째 줄에는

www.acmicpc.net

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


int main() {
	int a, b, c;
	int coke, sprite;
	cin >> a >> b >> c >> coke >> sprite;
	cout << min(min(a, b), c) + min(coke, sprite) - 50;
	return 0;
}
728x90

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

[백준] 3053번 택시 기하학  (0) 2020.03.07
[백준] 1002번 터렛  (0) 2020.03.07
[백준] 2206번 벽 부수고 이동하기  (0) 2020.03.03
[백준] 11816번 8진수, 10진수, 16진수  (0) 2020.03.03
[백준] 2752번 세수정렬  (0) 2020.03.03

+ Recent posts

티스토리툴바