코딩묻은 디자이너

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;
	}
	
}

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

문제

배열 A가 주어졌을 때, N번째 큰 값을 출력하는 프로그램을 작성하시오.

배열 A의 크기는 항상 10이고, 자연수만 가지고 있다. N은 항상 3이다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 배열 A에서 3번째 큰 값을 출력한다.

풀이

입력받은 배열을 내림차순으로 정렬해주고 3번째 값을 출력한다

파이썬으로 풀면 매매애ㅐㅐㅐㅐㅐㅐㅐ우 쉽게 풀 수 있는 문제였겠지만,,, 아직 배열을 받는게 어색해서 많은 시간 까지는 아니어두 조금 시간이 걸린 문제... 빨리 C++에 익숙해지면 좋겠다

코드

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

int main()
{
	int T;
	cin >> T;

	//num을 입력받아서 배열에 넣기
	for (int tc = 0; tc < T; tc++)
	{	
		vector<int>arr;
		for (int i = 0; i < 10; i++)
		{
			int num;
			cin >> num;
			arr.push_back(num);
		}
		//내림차순 정렬
		//임시로 숫자를 넣을 변수
		int temp;
		for (int i = 0; i < 10; i++)
		{
			for (int j = i + 1; j < 10; j++)
			{
				if (arr[i] < arr[j])
				{
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}

		}
		//count는 0부터 시작하기 때문에 3번로 큰 수의 인덱스는 2
		cout << arr[2] << '\n';
	}

}

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

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 S의 최솟값을 출력한다.

풀이

A와 B를 각각 오름차순/내림차순으로 정렬 한 후 각 인덱스 값을 계산해주었다

단, B에 있는 수는 재배열하면 안 된다.

는 조건이 붙어있으므로 따지고들면 틀린 코드이다...

코드

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

int main()
{
	int N, temp;
	vector<int>arrA;
	vector<int>arrB;

	cin >> N;

	// A 입력받기
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		arrA.push_back(num);
	}
	// B 입력받기
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		arrB.push_back(num);
	}
	// A, B를 오름차순, 내림차순으로 정렬
	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {
			if (arrA[i] > arrA[j]) {
				temp = arrA[i];
				arrA[i] = arrA[j];
				arrA[j] = temp;
			}
			if (arrB[i] < arrB[j]) {
				temp = arrB[i];
				arrB[i] = arrB[j];
				arrB[j] = temp;
			}
		}
	}
	// ans 에 값을 하나씩 더함
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		ans += arrA[i] * arrB[i];
	}
	cout << ans;
}

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

문제

두 양의 정수가 주어졌을 때, 첫 번째 수가 두 번째 수보다 큰지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 두 정수가 주어진다. 두 수는 백만보다 작거나 같은 양의 정수이다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스마다, 첫 번째 수가 두 번째 수보다 크면 Yes를, 아니면 No를 한 줄에 하나씩 출력한다.

풀이

코드 흐름 자체는 어렵지 않지만 왜인지 Yes / No가 계속 int 형식으로 출력돼서 고민을 하게 되었던 문제

C++ 에서는 작은 따옴표와 큰 따옴표를 구분해서 사용해야 했다

하나의 문자를 식별할 때 작은 따옴표

문자열을 식별할 때는 큰 따옴표

코드

#include<iostream>
using namespace std;

int main()
{
	int A, B;
	while (true)
	{
		cin >> A >> B;
		if (A == 0 && B == 0) break;
		if (A > B) cout << "Yes";
		else  cout << "No";
		cout << '\n';
	}
}

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

문제

수학자가 구를 깎아서 볼록다면체를 만들었다. 이 수학자는 임의의 볼록다면체에 대해 (꼭짓점의 수) - (모서리의 수) + (면의 수) = 2가 성립한다는 것을 알고 있다. 그래서 구를 깎는 게 취미인 이 사람은 꼭짓점, 모서리와 면의 수를 기록할 때 꼭짓점과 모서리의 수만 세고 면의 수는 세지 않는다.

입력

첫 번째 줄에 1 이상 100 이하의 자연수 T가 주어진다.

다음 T개의 줄에 4 이상 100 이하의 자연수 V와 E가 공백을 사이에 두고 주어진다. V와 E는 각각 꼭짓점의 개수와 모서리의 개수이다.

출력

각 V와 E에 대해 볼록다면체의 면의 수를 한 줄에 하나씩 출력한다.

풀이

(꼭짓점의 수) - (모서리의 수) + (면의수) = 2 라면

(면의 수) = 2 - V(꼭짓점의 수) + E(면의 수) 이다 

코드

#include<iostream>
using namespace std;

int main()
{
	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		int V, E;
		cin >> V >> E;
		cout << (2 - V + E) << '\n';
	}
}

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

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

풀이

위와 아래 부분을 나눠서 코드를 작성하였다

코드

#include<iostream>
using namespace std;
// 별 찍기 - 8

int main()
{
	int N;
	cin >> N;

	for (int i = 0; i < N-1; i++)
	{
		for (int j = 0; j < i+1; j++)
		{
			cout << '*';
		}
		for (int j = 0; j < N * 2 - ((i+1) * 2);j++)
		{
			cout << ' ';
		}
		for (int j = 0; j < i+1; j++)
		{
			cout << '*';
		}
		cout << '\n';
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N-i; j++)
		{
			cout << '*';
		}
		for (int j = 0; j < i * 2; j++)
		{
			cout << ' ';
		}
		for (int j = 0;j < N-i; j++)
		{
			cout << '*';
		}
		cout << '\n';
	}
}

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

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

풀이

유클리드 호제법을 사용해서 풀이한다

*유클리드 호제법*

최소공배수를 구하는 알고리즘

유클리드 호제법

두 양의 정수 a,b\ (a>b)a,b (a>b)에 대하여 a=bq+r\,\left(0\le r<b\right)a=bq+r(0≤r<b)[2]라 하면, a,ba,b의 최대공약수는 b,rb,r의 최대공약수와 같다. 즉,\gcd\left(a,\ b\right)=\gcd\left(b,\ r\right)gcd(a, b)=gcd(b, r)r=0r=0이라면, a,ba,b의 최대공약수는 bb가 된다.

인류 최초의 알고리즘이라고 한다 (신기)

최소공배수를 구해준 후 A, B 를 최소공배수로 나눈 수를 곱해준다

코드

#1934 최소 공배수
import sys

T = int(input())

for tc in range(T):
    A, B = map(int, sys.stdin.readline().split())
    a = A
    b = B
    while True:
        r = a % b
        if r == 0:
            break
        a = b
        b = r
    # 최소공배수 = b
    print((A//b)*(B//b)*b)

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

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

코드

#include<iostream>
using namespace std;

int main()
{
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < (N-1)-i; j++)
		{
			cout << ' ';
		}
		for (int j = 0; j < i * 2 +1;j++)
		{
			cout << '*';
		}
		cout << '\n';
	}
	for (int i = 0; i < N-1; i++)
	{
		for (int j = 0; j < i+1; j++)
		{
			cout << ' ';
		}
		for (int j = 0; j < (N-1-i)*2-1 ;j++)
		{
			cout << '*';
		}
		cout << '\n';
	}
}