문제 1 ) 카잉 달력
문제
최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.
예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.
네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.
출력
출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.
예제 입력 1
3
10 12 3 9
10 12 7 2
13 11 5 6
예제 출력 1
33
-1
83
내가 한 구현 -> 시간초과
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int T = Integer.parseInt(tokenizer.nextToken());
StringBuilder builder = new StringBuilder();
int M,N,x,y;
for (int i = 0; i < T; i++) {
tokenizer = new StringTokenizer(reader.readLine());
M = Integer.parseInt(tokenizer.nextToken());
N = Integer.parseInt(tokenizer.nextToken());
x = Integer.parseInt(tokenizer.nextToken());
y = Integer.parseInt(tokenizer.nextToken());
builder.append(find_year(M,N,x,y)+"\n");
}
System.out.println(builder);
}
private static int find_year(int m, int n, int x, int y) {
// TODO Auto-generated method stub
int year = 0;
int temp_x=0,temp_y=0;
while (true) {
if (temp_x == x && temp_y == y)
return year;
if(temp_x == m && temp_y == n)
return -1;
if (temp_x == m)
temp_x = 1;
else
temp_x++;
if (temp_y == n)
temp_y = 1;
else
temp_y++;
year++;
}
}
}
해결
1 ≤ M, N ≤ 40,000 이므로
경우의 수는 MN = 1,600,000,000가지라서 너무 많음
그래서 나머지 전략을 사용해야함
먼저 전체에 1을 빼야함
x = 0,1....,M-1
y = 0,1....,N-1
i: <i%M , i%N> 으로 표현 가능
23 : <23 % 5 , 23 % 7>
x=3 y=2 인것을 찾을때 하나는 고정해도 됨
x=3을 고정한다면 5번 만에 찾을 수있음
3<3,2> ,8<3,1>..23<3,2>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int T = Integer.parseInt(tokenizer.nextToken());
StringBuilder builder = new StringBuilder();
int M,N,x,y;
for (int i = 0; i < T; i++) {
tokenizer = new StringTokenizer(reader.readLine());
M = Integer.parseInt(tokenizer.nextToken());
N = Integer.parseInt(tokenizer.nextToken());
x = Integer.parseInt(tokenizer.nextToken());
y = Integer.parseInt(tokenizer.nextToken());
builder.append(find_year(M,N,x,y)+"\n");
}
System.out.println(builder);
}
private static int find_year(int m, int n, int x, int y) {
// TODO Auto-generated method stub
for(int i = x-1; i < (n*m); i+=m)//i에 m만큼 계속 더한다면
//m으로 나눈 나머지 = i x값 고정
{
if(i%n==(y-1))//x는 고정으로 했으니 y만 맞는 지 확인
{
return i+1;
}
}
return -1;
}
}
문제 2 ) 수 이어쓰기1
문제
1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.
출력
첫째 줄에 새로운 수의 자릿수를 출력한다.
예제 입력 1
120
예제 출력 1
252
풀이
1 ≤ N ≤ 100,000,000d 이기 때문에 오래 걸릴수 있다.
중복 되는 계산이 많다는 점을 이용해서 한번에 처리해야함
구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine());
int start=1;
int end=0;
int len=1;
int num=0;
for(int i=1; i<=N; i*=10)
{
end = (i*10)-1;
if(N<=end)
end = N;
num += (end-i+1)*len;
len++;
}
System.out.println(num);
}
}• 수의 자리수별로 나누어서 문제를 해결할수 있다
•N= 120
•1-9→(9-1+1)×1
• 10- 99→(99-10+1)×2
• 100- 120→(120-100+1)×3
