티어 : Silver 3 시간 제한 : 1 초 메모리 제한 : 128 MB 알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론
문제
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.
출력
1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.
예제 입출력
우선 알고리즘은 각 자릿수가 1로 이루어진 숫자로 n이 나누어 떨어질 때까지 확인하는 방식을 이용했다.
처음에는 각 자릿수가 1로 이루어진 숫자를 만들기 위해 문자열을 이용했다.
num이라는 string형 변수를 하나 만들어 n으로 나누어떨어지지 않으면 '1'을 추가해주는 방식으로 아래와 같이 구현했다.
#include <iostream>
#include <string>
using namespace std;
int cal_len(long long n){
string num = to_string(n);
return num.length();
}
long long ispossible(int n){
// n의 길이 계산
int len = cal_len(n);
string num;
// n의 길이만큼 1로만 구성된 문자열 만들기
for(int i=0;i<len;i++){
num += '1'; // O(n)으로 동작
}
while(true){
// num이 n의 배수인지 확인
if(num%n==0) return num.length();
// num 한 자리 추가
num += '1';
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
하지만 런타임 에러(out_of_range)로 실패 ㅠ
num += '1';의 연산이 O(n)으로 동작하기 때문에 연산량이 너무 많기 때문이다.
그래서 num 변수를 long long형으로 선언해 동일한 알고리즘을 사용했다.
#include <iostream>
using namespace std;
long long ispossible(int n){
int cnt=1;
long long num=1;
while(true){
// num이 n의 배수인지 확인
if(!(num%n)) return cnt;
// num 한 자리 추가
num = num*10+1;
cnt++;
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
하지만 이 방법도 동일하게 런타임 에러(out_of_range)가 났다.
결과적으로 런타임 에러의 원인은 num이 너무 커지는 것이었는데, num을 줄이기 위해 Moduler(%) 연산을 이용했다.
Algorithm
Brute Force 1. num(long long형)에 1로 이루어진 숫자를 하나씩 담음 2. num이 n으로 나누어 떨어지는지 확인 2-1. 나누어떨어지면 num의 길이 return 2-2. 나누어떨어지지 않으면 num의 길이 증가 (num = num*10 + 1 연산) → 이 때 moduler 연산(num%=n)을 이용해 num의 크기 줄여주는 것이 이 문제의 핵심 !
Code
#include <iostream>
using namespace std;
long long ispossible(int n){
int cnt=1;
long long num=1;
while(true){
// num이 n의 배수인지 확인
if(!(num%n)) return cnt;
// num의 크기 줄여주기
num%=n;
// num 한 자리 추가
num = num*10+1;
cnt++;
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // cin.eof(): EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
티어 : Silver 4 시간 제한 : 2 초 메모리 제한 :128 MB 알고리즘 분류 : 수학, 그리디 알고리즘, 정렬
문제
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 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의 최솟값을 출력한다.
예제 입출력
Algorithm
정렬 1. A 배열 오름차순 정렬 2. B 배열 내림차순 정렬 3. S = {A의 최솟값 * B의 최댓값}의 합
Code
N = int(input())
A = [int(num) for num in input().split()]
B = [int(num) for num in input().split()]
# A 배열 오름차순, B 배열 내림차순
A.sort()
B.sort(reverse=True)
# S = A최솟값 * B최댓값
S = 0
for idx in range(N):
S += A[idx] * B[idx]
print(S)
