코딩묻은 디자이너

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/10178

문제

할로윈데이에 한신이네는 아부지가 사탕을 나눠주신다. 하지만 한신이의 형제들은 서로 사이가 좋지않아 서른이 넘어서도 사탕을 공정하게 나누어 주지 않으면 서로 싸움이 난다. 매년 할로윈데이때마다 아부지는 사탕을 자식들에게 최대한 많은 사탕을 나누어 주시기 원하며 자신에게는 몇개가 남게되는지에 알고 싶어 하신다. 이런 아부지를 도와서 형제간의 싸움을 막아보자.

입력

가장 첫 번째 줄에는 테스트 케이스의 수가 입력되고, 각 테스트 케이스마다 사탕의 개수 c와 형제의 수 v가 차례대로 입력된다.

출력

출력은 예제를 보고 ”You get __ piece(s) and your dad gets __ piece(s).” 형식에 맞추어 적절하게 출력하라.

풀이

C++에서의 / 와 % 를 알고 있다면 쉽게 풀 수 있는 문제

/ 는 몫을 % 는 나머지를 구할 수 있다

코드

#include<iostream>
using namespace std;

int main()
{
	int N, c, v;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> c >> v;
		cout << "You get " << c / v << " piece(s) and your dad gets " << c % v << " piece(s)." << '\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';
	}
}

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

문제

동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.

이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.

하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.

입력

첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.

출력

첫 줄에 구간에 속하는 숫자의 합을 출력한다.

풀이

vector에 1, 2, 2, 3, 3, 3, 4... 에 해당하는 숫자를 미리 넣어두고

만들어진 arr를 돌면서 범위에 해당하는 숫자를 결과값에 더해준다

코드

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

int main()
{	
	int A, B, cnt = 0, num = 1;
	cin >> A >> B;
	vector<int>arr;

	// 배열이 1000개의 입력값을 다 받을 필요가 없으므로 입력같은 B 값으로 범위를 제한해준다
	while (cnt < B)
	{	
    	// 현재 num 만큼 돌며 벡터에 추가해준다
		for (int i = 0; i < num;i++)
		{	
			arr.push_back(num);
            // 만약 B 보다 벡터에 입력받은 수가 많아지면 while문을 탈출한다
			cnt++;
			if (cnt > B) break;
		}
		num++;
	}
	int ans = 0;
    // 인덱스는 0부터 시작하기 때문에 A번째 값을 받아오기 위해서는 -1를 빼준다
	for (int i = A-1; i < B; i++)
	{
		ans += arr[i];
	}
	cout << ans;
}

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

문제

OX 문제는 맞거나 틀린 두 경우의 답을 가지는 문제를 말한다. 여러 개의 OX 문제로 만들어진 시험에서 연속적으로 답을 맞히는 경우에는 가산점을 주기 위해서 다음과 같이 점수 계산을 하기로 하였다. 1번 문제가 맞는 경우에는 1점으로 계산한다. 앞의 문제에 대해서는 답을 틀리다가 답이 맞는 처음 문제는 1점으로 계산한다. 또한, 연속으로 문제의 답이 맞는 경우에서 두 번째 문제는 2점, 세 번째 문제는 3점, ..., K번째 문제는 K점으로 계산한다. 틀린 문제는 0점으로 계산한다.

예를 들어, 아래와 같이 10 개의 OX 문제에서 답이 맞은 문제의 경우에는 1로 표시하고, 틀린 경우에는 0으로 표시하였을 때, 점수 계산은 아래 표와 같이 계산되어, 총 점수는 1+1+2+3+1+2=10 점이다.

채점점수

시험문제의 채점 결과가 주어졌을 때, 총 점수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 문제의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 N개 문제의 채점 결과를 나타내는 0 혹은 1이 빈 칸을 사이에 두고 주어진다. 0은 문제의 답이 틀린 경우이고, 1은 문제의 답이 맞는 경우이다. 

출력

첫째 줄에 입력에서 주어진 채점 결과에 대하여 가산점을 고려한 총 점수를 출력한다.

풀이

vector에 값을 넣어준 후 더해질 score값을 선언한다

답이 맞다면 score값을 총 점수에 더한 후 1을 더한다

답이 틀리다면 score값을 1로 초기화 한다

코드

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

int main()
{
	int N;
	cin >> N;
	vector<int>arr;
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		arr.push_back(num);
	}
	int score = 1;
	for (int i = 0;i < N;i++)
	{
		// 맞다면 점수를 더하고 점수값에 1을 더한다
		if (arr[i] == 1)
		{
			ans = ans + score;
			score++;
		}
		// 틀리면 더해지는 점수를 초기화한다
		else
		{
			score = 1;
		}
	}
	cout << ans;
}

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

문제

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.

6을 예로 들면

• 6 ÷ 1 = 6 … 0
• 6 ÷ 2 = 3 … 0
• 6 ÷ 3 = 2 … 0
• 6 ÷ 4 = 1 … 2
• 6 ÷ 5 = 1 … 1
• 6 ÷ 6 = 1 … 0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.

두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

출력

첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.

풀이

많은 방법으로 풀이를 시도하였다

1. while문을 사용하여 입력받은 수를 1부터 차례로 나눈 후 나머지가 0인 값을 vector에 넣고 vector에서 K번째 값을 출력하도록 하였다 => 실패

2. 혹시 vector내에 너무 큰 수가 들어와서 시간 초과가 나는가 싶어 N/2로 while범위를 줄이고 나머지가 0이되는 나누는 값과 나눠진 값을 vector에 넣은 후 다시 vector을 오름차순으로 정렬하여 k번째값 출력 => 실패 (너무 복잡)

3. while문을 돌며 나머지 값이 0이 되면 K--를 해줘서 반복문이 최대한 안돌도록 하고 k가 0인 순간 num을 출력 => 실패

4. 마지막으로 while문을 for 문으로 변경 => 성공

사실 성공 했지만 왜 성공했는지 모르겠다 왜 while은 안되는건데! 이유라도 알았으면 몰라... 혹시 처리 안된 예외가 있나 한참 살핀 시간이 아깝다.

코드

#include<iostream>
using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;
	int num = 1;

	for (int i = 0; i < N ;i++)
	{
		if (N % num == 0)
		{
			K--;
		}
		if (K == 0) break;
		num++;
	}
	if (K > 0)
	{
		cout << '0';
	}
	else
	{
		cout << num;
	}
	
}