문제

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 

예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.

n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.

입력

입력은 테스트 케이스마다 한 줄 간격으로 n이 주어진다. (2 < n < 100, 000)

입력의 마지막엔 -1이 주어진다.

출력

테스트케이스 마다 한줄에 하나씩 출력해야 한다.

n이 완전수라면, n을 n이 아닌 약수들의 합으로 나타내어 출력한다(예제 출력 참고).

이때, 약수들은 오름차순으로 나열해야 한다.

n이 완전수가 아니라면 n is NOT perfect. 를 출력한다.

예제 입력 1

6
12
28
-1

예제 출력 1

6 = 1 + 2 + 3
12 is NOT perfect.
28 = 1 + 2 + 4 + 7 + 14
더보기

Solution

#include<stdio.h>

int main(void)
{
	int n;

	scanf("%d", &n);

	while(n!=-1)
	{
		int sum=0;

		for(int i=1;i*2<=n;i++)
			if(n%i==0)
				sum+=i;

		if(sum==n)
		{
			printf("%d = 1", n);

			for(int i=2;i*2<=n;i++)
				if(n%i==0)
					printf(" + %d", i);
			printf("\n");
		}
		else
			printf("%d is NOT perfect.\n", n);

		scanf("%d", &n);
	}

	return 0;
}
728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 3053번: 택시 기하학  (0) 2020.10.20
<백준 알고리즘> 11866번: 요세푸스 문제 0  (0) 2020.10.19
<백준 알고리즘> 5347번: LCM  (0) 2020.10.17
<백준 알고리즘> 8979번: 올림픽  (0) 2020.10.17
<백준 알고리즘> 11772번: POT  (0) 2020.10.17

문제

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

입력

첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다.

예제 입력 1

3
15 21
33 22
9 10

예제 출력 1

105
66
90
더보기

Solution

#include<stdio.h>

unsigned long long int gcd(unsigned long long int x,unsigned long long int y)
{
	if(x<y)
	{
		unsigned long long int temp=x;
		x=y;
		y=temp;
	}

	while(y!=0)
	{
		unsigned long long int temp=x%y;
		x=y;
		y=temp;
	}

	return x;
}

unsigned long long int lcm(unsigned long long int x,unsigned long long int y)
{
	return x*y/gcd(x,y);
}

int main(void)
{
	int n;

	scanf("%d", &n);

	for(int i=0;i<n;i++)
	{
		unsigned long long int a, b;

		scanf("%llu %llu", &a, &b);

		printf("%llu\n", lcm(a,b));
	}

	return 0;
}
728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 11866번: 요세푸스 문제 0  (0) 2020.10.19
<백준 알고리즘> 9506번: 약수들의 합  (0) 2020.10.17
<백준 알고리즘> 8979번: 올림픽  (0) 2020.10.17
<백준 알고리즘> 11772번: POT  (0) 2020.10.17
<백준 알고리즘> 10539번: 수빈이와 수열  (0) 2020.10.17

문제

올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다.

  1. 금메달 수가 더 많은 나라 
  2. 금메달 수가 같으면, 은메달 수가 더 많은 나라
  3. 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 

각 국가는 1부터 N 사이의 정수로 표현된다. 한 국가의 등수는 (자신보다 더 잘한 나라 수) + 1로 정의된다. 만약 두 나라가 금, 은, 동메달 수가 모두 같다면 두 나라의 등수는 같다. 예를 들어, 1번 국가가 금메달 1개, 은메달 1개를 얻었고, 2번 국가와 3번 국가가 모두 은메달 1개를 얻었으며, 4번 국가는 메달을 얻지 못하였다면, 1번 국가가 1등, 2번 국가와 3번 국가가 공동 2등, 4번 국가가 4등이 된다. 이 경우 3등은 없다. 

각 국가의 금, 은, 동메달 정보를 입력받아서, 어느 국가가 몇 등을 했는지 알려주는 프로그램을 작성하시오. 

입력

입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 국가를 나타내는 정수와 이 국가가 얻은 금, 은, 동메달의 수가 빈칸을 사이에 두고 주어진다. 전체 메달 수의 총합은 1,000,000 이하이다.

출력

출력은 단 한 줄이며, 입력받은 국가 K의 등수를 하나의 정수로 출력한다. 등수는 반드시 문제에서 정의된 방식을 따라야 한다. 

예제 입력 1

4 3
1 1 2 0
2 0 1 0
3 0 1 0
4 0 0 1

예제 출력 1

2

예제 입력 2

4 2
1 3 0 0
3 0 0 2
4 0 2 0
2 0 2 0

예제 출력 2

2
더보기

Solution

#include<stdio.h>
#include<stdlib.h>

typedef struct
{
	int number;
	int gold;
	int silver;
	int bronze;
	int rank;
}
country;

int main(void)
{
	int N, K;
	country *list=NULL;

	scanf("%d %d", &N, &K);
	list=(country *)malloc(N*sizeof(country));

	for(int i=0;i<N;i++)
	{
		scanf("%d %d %d %d", &list[i].number, &list[i].gold, &list[i].silver, &list[i].bronze);
		list[i].rank=i+1;
	}

	for(int i=0;i<N-1;i++)
		for(int j=i+1;j<N;j++)
			if(list[i].gold<list[j].gold)
			{
				int temp=list[i].number;
				list[i].number=list[j].number;
				list[j].number=temp;
				temp=list[i].gold;
				list[i].gold=list[j].gold;
				list[j].gold=temp;
				temp=list[i].silver;
				list[i].silver=list[j].silver;
				list[j].silver=temp;
				temp=list[i].bronze;
				list[i].bronze=list[j].bronze;
				list[j].bronze=temp;
			}
			else if(list[i].gold==list[j].gold)
			{
				if(list[i].silver<list[j].silver)
				{
					int temp=list[i].number;
					list[i].number=list[j].number;
					list[j].number=temp;
					temp=list[i].gold;
					list[i].gold=list[j].gold;
					list[j].gold=temp;
					temp=list[i].silver;
					list[i].silver=list[j].silver;
					list[j].silver=temp;
					temp=list[i].bronze;
					list[i].bronze=list[j].bronze;
					list[j].bronze=temp;
				}
				else if(list[i].silver==list[j].silver)
				{
					if(list[i].bronze<list[j].bronze)
					{
						int temp=list[i].number;
						list[i].number=list[j].number;
						list[j].number=temp;
						temp=list[i].gold;
						list[i].gold=list[j].gold;
						list[j].gold=temp;
						temp=list[i].silver;
						list[i].silver=list[j].silver;
						list[j].silver=temp;
						temp=list[i].bronze;
						list[i].bronze=list[j].bronze;
						list[j].bronze=temp;
					}
				}
			}

	for(int i=0;i<N-1;i++)
		if(list[i].gold==list[i+1].gold && list[i].silver==list[i+1].silver && list[i].bronze==list[i+1].bronze)
			list[i+1].rank=list[i].rank;

	for(int i=0;i<N;i++)
		if(list[i].number==K)
		{
			printf("%d\n", list[i].rank);
			break;
		}
	free(list);
	return 0;
}
728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 9506번: 약수들의 합  (0) 2020.10.17
<백준 알고리즘> 5347번: LCM  (0) 2020.10.17
<백준 알고리즘> 11772번: POT  (0) 2020.10.17
<백준 알고리즘> 10539번: 수빈이와 수열  (0) 2020.10.17
<백준 알고리즘> 5596번: 시험 점수  (0) 2020.10.16

문제

The teacher has sent an e-mail to her students with the following task:

"Write a programme that will determine and output the value of  if given the statement:

 

X = (number1)^pot1 + (number2)^pot2 + … + (numberN)^potN

 

and it holds that number1, number2 to numberN are integers, and pot1, pot2 to potN one-digit integers." Unfortunately, when the teacher downloaded the task to her computer, the text formatting was lost so the task transformed into a sum of N integers:

 

X = P1 + P2 + … Pn

 

For example, without text formatting, the original task in the form of  X = 21^2 + 125^3 became a task in the form of X = 212 + 1253. Help the teacher by writing a programme that will, for given N integers from P1 to PN determine and output the value of X from the original task.

Please note: We know that it holds a N = a ㆍ a ㆍ…ㆍ a (N times).

입력

The first line of input contains the integer N (1 ≤ N ≤ 10), the number of the addends from the task. Each of the following N lines contains the integer Pi (10 ≤ Pi ≤ 9999,  = 1 ... N) from the task.

출력

The first and only line of output must contain the value of X (X ≤ 1 000 000 000) from the original task.

예제 입력 1

2
212
1253

예제 출력 1

1953566

예제 입력 2

5
23
17
43
52
22

예제 출력 2

102

예제 입력 3

3
213
102
45

예제 출력 3

10385

힌트

Clarification of the first example: 21^2 + 125^3 = 441 + 1953125 = 1953566.

더보기

Solution

#include<stdio.h>

int main(void)
{
	int N, P, X=0;

	scanf("%d", &N);

	for(int i=0;i<N;i++)
	{
		int mul=1, square;

		scanf("%d", &P);

		square=P%10;
		P/=10;

		for(int j=0;j<square;j++)
			mul*=P;

		X+=mul;
	}

	printf("%d\n", X);
	return 0;
}
728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 5347번: LCM  (0) 2020.10.17
<백준 알고리즘> 8979번: 올림픽  (0) 2020.10.17
<백준 알고리즘> 10539번: 수빈이와 수열  (0) 2020.10.17
<백준 알고리즘> 5596번: 시험 점수  (0) 2020.10.16
<백준 알고리즘> 2164번: 카드2  (0) 2020.10.16

문제

수빈이는 심심해서 수열을 가지고 놀고 있다. 먼저, 정수 수열 A를 쓴다. 그리고 그 아래에 정수 수열 A의 해당 항까지의 평균값을 그 항으로 하는 정수 수열 B를 쓴다. 

예를 들어, 수열 A가 1, 3, 2, 6, 8이라면, 수열 B는 1/1, (1+3)/2, (1+3+2)/3, (1+3+2+6)/4, (1+3+2+6+8)/5, 즉, 1, 2, 2, 3, 4가 된다. 

수열 B가 주어질 때, 수빈이의 규칙에 따른 수열 A는 뭘까?

입력

첫째 줄에는 수열 B의 길이만큼 정수 N(1 ≤ N ≤ 100)이 주어지고, 둘째 줄에는 수열 Bi를 이루는 N개의 정수가 주어진다. (1 ≤ Bi ≤ 10^9)

출력

첫째 줄에는 수열 A를 이루는 N개의 정수를 출력한다. (1 ≤ Ai ≤ 10^9)

예제 입력 1

1
2

예제 출력 1

2

예제 입력 2

4
3 2 3 5

예제 출력 2

3 1 5 11

예제 입력 3

5
1 2 2 3 4

예제 출력 3

1 3 2 6 8
더보기

Solution

#include<stdio.h>
#include<stdlib.h>

int main(void)
{
	int N, *A=NULL, *B=NULL;

	scanf("%d", &N);
	A=(int *)malloc(N*sizeof(int));
	B=(int *)malloc(N*sizeof(int));

	scanf("%d", &B[0]);
	A[0]=B[0];
	for(int i=1;i<N;i++)
	{
		scanf("%d", &B[i]);
		A[i]=(i+1)*B[i]-i*B[i-1];
	}

	for(int i=0;i<N;i++)
		printf("%d ", A[i]);
	printf("\n");
	free(A);
	free(B);
	return 0;
}
728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 8979번: 올림픽  (0) 2020.10.17
<백준 알고리즘> 11772번: POT  (0) 2020.10.17
<백준 알고리즘> 5596번: 시험 점수  (0) 2020.10.16
<백준 알고리즘> 2164번: 카드2  (0) 2020.10.16
<백준 알고리즘> 2822번: 점수 계산  (0) 2020.10.16

문제

대한고등학교에 재학 중인 민국이와 만세는 4과목(정보, 수학, 과학, 영어)에 대한 시험을 봤습니다. 민국이와 만세가 본 4과목의 점수를 입력하면, 민국이의 총점 S와 만세의 총점 T 중에서 큰 점수를 출력하는 프로그램을 작성하세요. 다만, 서로 동점일 때는 민국이의 총점 S를 출력하세요.

입력

입력은 2줄로 이루어져 있습니다.

1번째 줄에는 순서대로 민국이의 정보, 수학, 과학, 영어 점수(정수형)를 입력하는데, 이때 공백을 끊어서 구분합니다.

2번째 줄에는 마찬가지로 순서대로 만세의 정보, 수학, 과학, 영어 점수(정수형)를 입력하고 위와 같이 공백을 끊어서 구분합니다.

출력

출력은 문제에서 제시했던 방법대로 구하면 됩니다.

예제 입력 1

100 80 70 60
80 70 80 90

예제 출력 1

320
더보기

Solution

#include<stdio.h>

int main(void)
{
	int score, S=0, T=0;

	for(int i=0;i<4;i++)
	{
		scanf("%d", &score);
		S+=score;
	}
	for(int i=0;i<4;i++)
	{
		scanf("%d", &score);
		T+=score;
	}

	printf("%d\n", T>S?T:S);
	return 0;
}
728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 11772번: POT  (0) 2020.10.17
<백준 알고리즘> 10539번: 수빈이와 수열  (0) 2020.10.17
<백준 알고리즘> 2164번: 카드2  (0) 2020.10.16
<백준 알고리즘> 2822번: 점수 계산  (0) 2020.10.16
<백준 알고리즘> 20001번: 고무오리 디버깅  (0) 2020.10.15

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1≤N≤500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

예제 입력 1

6

예제 출력 1

4
더보기

Solution - O(N)

#include<stdio.h>

int main(void)
{
	int N;

	scanf("%d", &N);

	if(N<3)
		printf("%d\n", N);
	else
	{
		int state=0;

		for(int i=3;i<=N;i++)
			if(state+2<=i)
				state+=2;
			else
				state=2;

		printf("%d\n", state);
	}

	return 0;
}
더보기

Solution - O(N)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();

		int N=Integer.parseInt(br.readLine());
		
		if(N<3)
			System.out.println(N);
		else {
			int state=0;
			
			for(int i=3;i<=N;i++)
				state=state+2<=i?state+2:2;
			
			System.out.println(state);
		}
	}
}
더보기

Solution - O(log N)

#include<stdio.h>

int main(void)
{
	int N;

	scanf("%d", &N);

	if(N<3)
		printf("%d\n", N);
	else
	{
		int index=0;

		while(1<<++index<N);
		N-=1<<index-1;

		printf("%d\n", N<<1);
	}

	return 0;
}
더보기

Solution - O(log N)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

		int N=Integer.parseInt(br.readLine());
		
		if(N<3)
			System.out.println(N);
		else {
			int index=0;
			
			while(1<<++index<N);
			N-=1<<index-1;
			
			System.out.println(N<<1);
		}
	}
}
더보기

Solution - O(log N) or O(1) -> log함수의 시간복잡도에 따라 나뉨

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		double log=Math.log(N)/Math.log(2);

		System.out.println((N<3||log==(int)log)?N:N-(1<<(int)log)<<1);
	}
}

 

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 10539번: 수빈이와 수열  (0) 2020.10.17
<백준 알고리즘> 5596번: 시험 점수  (0) 2020.10.16
<백준 알고리즘> 2822번: 점수 계산  (0) 2020.10.16
<백준 알고리즘> 20001번: 고무오리 디버깅  (0) 2020.10.15
<백준 알고리즘> 3036번: 링  (0) 2020.10.14

문제

상근이는 퀴즈쇼의 PD이다. 이 퀴즈쇼의 참가자는 총 8개 문제를 푼다. 참가자는 각 문제를 풀고, 그 문제를 풀었을 때 얻는 점수는 문제를 풀기 시작한 시간부터 경과한 시간과 난이도로 결정한다. 문제를 풀지 못한 경우에는 0점을 받는다. 참가자의 총 점수는 가장 높은 점수 5개의 합이다. 

상근이는 잠시 여자친구와 전화 통화를 하느라 참가자의 점수를 계산하지 않고 있었다. 참가자의 8개 문제 점수가 주어졌을 때, 총 점수를 구하는 프로그램을 작성하시오.

입력

8개 줄에 걸쳐서 각 문제에 대한 참가자의 점수가 주어진다. 점수는 0보다 크거나 같고, 150보다 작거나 같다. 모든 문제에 대한 점수는 서로 다르다. 입력으로 주어지는 순서대로 1번 문제, 2번 문제, ... 8번 문제이다.

출력

첫째 줄에 참가자의 총점을 출력한다. 둘째 줄에는 어떤 문제가 최종 점수에 포함되는지를 공백으로 구분하여 출력한다. 출력은 문제 번호가 증가하는 순서이어야 한다.

예제 입력 1

20
30
50
48
33
66
0
64

예제 출력 1

261
3 4 5 6 8
더보기

Solution

#include<stdio.h>
#include<stdlib.h>

int compare(const void *x,const void *y)
{
	return *(int *)x>*(int *)y?1:*(int *)x==*(int *)y?0:-1;
}

int main(void)
{
	int score[8], sorted[8], sum=0;

	for(int i=0;i<8;i++)
	{
		scanf("%d", &score[i]);
		sorted[i]=score[i];
	}

	qsort((void *)sorted,(size_t)8,sizeof(int),compare);

	for(int i=3;i<8;i++)
		sum+=sorted[i];

	printf("%d\n", sum);
	for(int i=0;i<8;i++)
		for(int j=3;j<8;j++)
			if(score[i]==sorted[j])
			{
				printf("%d ", i+1);
				break;
			}
	printf("\n");
	return 0;
}
728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 5596번: 시험 점수  (0) 2020.10.16
<백준 알고리즘> 2164번: 카드2  (0) 2020.10.16
<백준 알고리즘> 20001번: 고무오리 디버깅  (0) 2020.10.15
<백준 알고리즘> 3036번: 링  (0) 2020.10.14
<백준 알고리즘> 1476번: 날짜 계산  (0) 2020.10.13

+ Recent posts

티스토리툴바