코딩묻은 디자이너

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

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

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

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

풀이

실제 화폐 단위는 큰 수부터 빼주면서 진행하면 최솟값을 찾을 수 있다

코드

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

int main()
{
	int N, K;
	cin >> N >> K;
	vector<int>wallet;

	for (int i = 0; i < N ; i++)
	{
		int money;
		cin >> money;
		wallet.push_back(money);
	}
	int cnt = 0;
	for (int i = N-1; i >= 0; i--)
	{
		while (K >= wallet[i])
		{
			K = K - wallet[i];
			//cout << "K 값 :" << K << '\n';
			cnt++;
		}
	}
	cout << cnt;
}

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

문제

한상덕은 이번에 중덕 고등학교에 새로 부임한 교장 선생님이다. 교장 선생님으로서 첫 번째 일은 각 반의 수학 시험 성적의 통계를 내는 일이다.

중덕 고등학교 각 반의 학생들의 수학 시험 성적이 주어졌을 때, 최대 점수, 최소 점수, 점수 차이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 중덕 고등학교에 있는 반의 수 K (1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 각 반의 학생수 N (2 ≤ N ≤ 50)과 각 학생의 수학 성적이 주어진다. 시험 성적은 0보다 크거나 같고, 100보다 작거나 같은 정수이고, 공백으로 나누어져 있다. 

출력

각 반에 대한 출력은 다음과 같이 두 줄로 이루어져 있다.

• 첫째 줄에는 "Class X"를 출력한다. X는 반의 번호이며 입력으로 주어진 순서대로 1부터 증가한다.
• 둘째 줄에는 가장 높은 점수, 낮은 점수, 성적을 내림차순으로 정렬했을 때 가장 큰 인접한 점수 차이를 예제 출력과 같은 형식으로 출력한다.

풀이

sort를 이용해 정렬 한 후 계산한다

코드

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

int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int student, max_gap = 0;
		cin >> student;
		vector<int>arr;
		for (int j = 0; j < student; j++)
		{
			int score, gap = 0;
			cin >> score;
			arr.push_back(score);
		}
		sort(arr.begin(), arr.end());
		for (int j = 0; j < student; j++)
		{
			int gap = 0;
			if (j >= 1)
			{
				gap = arr[j] - arr[j - 1];
				if (gap > max_gap)
				{
					max_gap = gap;
				}
			}
		}
		cout << "Class " << i + 1<<"\n";
		cout << "Max " << arr.back() << ", Min " << arr.front() << ", Largest gap " << max_gap << "\n";
	}
}

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

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

풀이

stack 자료구조를 이용하여 풀었다

코드

// 스택을 이용한 알고리즘 풀이
#include<iostream>
#include<stack>
using namespace std;

int main()
{
	int N, ans = 0;
	stack<int>arr;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		// 만약 num이 0이면 이전 숫자를 합에서 빼고 해당 숫자 삭제
		if (num == 0)
		{	
			ans = ans - arr.top();
			arr.pop();
		}
		// 0이 아니면 stack에 추가
		else
		{
			arr.push(num);
			ans = ans + num;
		}
	}
	cout << ans;
}// 스택을 이용한 알고리즘 풀이
#include<iostream>
#include<stack>
using namespace std;

int main()
{
	int N, ans = 0;
	stack<int>arr;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		// 만약 num이 0이면 이전 숫자를 합에서 빼고 해당 숫자 삭제
		if (num == 0)
		{	
			ans = ans - arr.top();
			arr.pop();
		}
		// 0이 아니면 stack에 추가
		else
		{
			arr.push(num);
			ans = ans + num;
		}
	}
	cout << ans;
}

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

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

풀이

1과 자기자신의 수를 제외한 약수중 가장 작은 수와 가장 큰 수를 곱하면 답이 출력된다

입력을 받은 후 정렬을 하고, 곱해주었다

코드

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

int main()
{
	int N;
	cin >> N;
	vector<int>nums;

	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		nums.push_back(num);
	}
	sort(nums.begin(), nums.end());
	// vector의 가장 첫 원소
	//cout << nums.front();
	// vector의 가장 마지막 원소
	//cout << nums.back();
	cout << nums.front() * nums.back();
}

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

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

풀이

시간복잡도가 효율적인 정렬 알고리즘을 사용해서 풀 수 도 있지만

c++에서 제공하는 sort 알고리즘을 한번도 사용해본적도 없고 사용할줄도 몰라서 연습삼아 sort를 이용해서 풀었다.

추후 정렬알고리즘을 사용하는 방법도 업로드할 예정이다

2022.02.20 - [study/백준] - [백준] 2750. 수 정렬하기 : C++

수 정렬하기 1에서 처럼 무식하게 하나하나 비교하며 코드를 짤 경우 시간초과다

우선 sort를 사용하기 위해서는 algorithm을 include해야한다.

vector로 만들어진 배열의 경우엔 sort(배열이름.begin(),배열이름.end())로 배열의 시작과 끝을 입력해주어야 했다.

코드

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

int main()
{
	vector<int>arr;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		arr.push_back(num);
	}
	sort(arr.begin(),arr.end());
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << '\n';
	}
}

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

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

풀이

이중for문으로

하나하나 모두 비교해가며 i번째수가 크다면 위치를 바꾸는 방법으로 진행

모든 수를 비교해야하기 때문에 시간이 오래걸린다.

적은 수를 비교할 때는 편하게 사용한다(나는)

코드

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

int main()
{
	int N;
	cin >> N;
	vector<int>arr;

	for (int i = 0; i < N; i++)
	{
		int num;

		cin >> num;
		arr.push_back(num);
	}
	int temp;
	for (int i = 0; i < N;i++)
	{
		for (int j = i+1; j < N; j++)
		{
			if (arr[i] > arr[j])
			{
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << '\n';
	}
}

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

문제

7개의 자연수가 주어질 때, 이들 중 홀수인 자연수들을 모두 골라 그 합을 구하고, 고른 홀수들 중 최솟값을 찾는 프로그램을 작성하시오.

예를 들어, 7개의 자연수 12, 77, 38, 41, 53, 92, 85가 주어지면 이들 중 홀수는 77, 41, 53, 85이므로 그 합은

77 + 41 + 53 + 85 = 256

이 되고,

41 < 53 < 77 < 85

이므로 홀수들 중 최솟값은 41이 된다.

입력

입력의 첫째 줄부터 일곱 번째 줄까지 한 줄에 하나의 자연수가 주어진다. 주어지는 자연수는 100보다 작다.

출력

홀수가 존재하지 않는 경우에는 첫째 줄에 -1을 출력한다. 홀수가 존재하는 경우 첫째 줄에 홀수들의 합을 출력하고, 둘째 줄에 홀수들 중 최솟값을 출력한다.

풀이

나머지가 1인 수를 모두 plus_ans에 더해주고 자연수가 100보다 작은 수가 주어지기 때문에 min_ans를 100으로 초기화 한 후 홀수인 수가 min_ans보다 작으면 min_ans를 갱신한다

최종적으로 plus_ans 가 0보다 크지 않으면 홀수인 값이 없는 경우가 되므로 -1을 출력한다

코드

#include<iostream>
using namespace std;

int main()
{	
	int plus_ans = 0, min_ans = 100;
	for (int i = 0; i < 7; i++)
	{
		int num;
		cin >> num;
		// 나머지가 1이면
		if (num % 2 == 1)
		{
			plus_ans = plus_ans + num;
			//최소값보다 값이 작으면
			if (num < min_ans)
			{
				min_ans = num;
			}
		}
	}
	if (plus_ans > 0)
	{
		cout << plus_ans << '\n' << min_ans << '\n';
	}
	else cout << "-1" << '\n';
	
}

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

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

C++ 풀이

받고있는 숫자의 중간에 공백이 없어서 이 숫자를 어떻게 배열로 정렬을하지...? 하다가

str형으로 문자정렬을 한 후 출력하는 방향으로 진행하였다

C++ 코드

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

int main()
{
	string num;
	int n;
	cin >> n;
	num = to_string(n);
    // 변환 되었는지 확인해보기
	// cout << num;
	
    // 문자열의 길이만큼 반복하며 수를 정렬
	for (int i = 0; i < num.length();i++)
	{	
		int temp;
		for (int j = i+1; j < num.length();j++)
		{
			if (num[i] < num[j])
			{
				temp = num[i];
				num[i] = num[j];
				num[j] = temp;
			}
		}
	}
	for (int i = 0; i < num.length(); i++)
	{
		cout << num[i];
	}
}

python 풀이

python 코드 역시 문자열로 입력받았다

*num으로 바로 출력하려고 했으나 '4 3 2 1' 이런 식으로 공백이 생겨서 for문을 통해 출력했다

python 코드

# 1427 소트인사이드

num = list(input())

for i in range(len(num)):
    for j in range(i,len(num)):
        if num[i] < num[j]:
            num[i], num[j] = num[j], num[i]

# print(*num)
for i in range(len(num)):
    print(num[i],end='')

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

문제

해빈이는 학교를 다니면서 틈틈히 번 돈으로 자동차를 사려고 한다. 자동차에 여러 가지 옵션을 포함시킬 수 있는데 해빈이는 덧셈과 곱셈을 하지 못하기 때문에 친구 태완이에게 도움을 청했다. 하지만 태완이도 덧셈과 곱셈을 못한다. 불쌍한 이 두 친구를 위해 모든 옵션이 주어진 자동차를 구매하는데 필요한 액수를 계산해 주자.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫 줄엔 자동차의 가격 s가 주어진다. (1 ≤ s ≤ 100 000)

둘째 줄엔 해빈이가 구매하려고 하는 서로 다른 옵션의 개수 n이 주어진다. (0 ≤ n ≤ 1 000)

뒤이어 n개의 줄이 입력으로 들어온다. 각 줄은 q 와 p로 이루어져 있는데 q는 해빈이가 사려고 하는 특정 옵션의 개수이고 p는 해당 옵션의 가격이다. (1 ≤ q ≤ 100, 1 ≤ p ≤ 10 000)

출력

각 테스트 케이스 마다, 해빈이가 최종적으로 구매하려는 자동차의 가격을 한줄씩 출력한다.

풀이

사칙연산을 하는 간단한 문제

코드

#include<iostream>
using namespace std;

int main()
{
	int T;
	cin >> T;
	for (int i=0; i < T; i++)
	{
		int s, n, ans = 0;
		cin >> s >> n;
		ans = ans + s;
		for (int j=0; j < n; j++)
		{
			int q, p;
			cin >> q >> p;
			ans = ans + (q * p);
		}
		cout << ans << '\n';
	}
}

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

문제

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

출력

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

풀이

입력받은 a값을 b만큼 제곱한 후 계산을 하면 계산 가능한 범위를 초과하게 된다.

그러므로 a를 b만큼 곱하는 도중 % 10을 해준다

C++은 python의 ** 같은 제곱근을 바로 계산해주는게 없었다(충격)

그리고 // 같은 몫'만' 계산하는것도 없고(충격, 하긴 당연함 저게 주석 표시니깐)

이러한 부분들을 정리해 볼 필요가 있는 것 같다

코드

#include<iostream>
using namespace std;

int main()
{
	int N, a, b;
	cin >> N;
	for (int i = 0; i < N; i++)
	{	
		int ans = 1;
		cin >> a >> b;
		for (int j = 0; j < b ;j++)
		{
			ans = (ans * a) % 10;
		}
		if (ans == 0) cout << "10" << '\n';
		else cout << ans%10 << '\n';
	}
}