[코딩테스트] 브루트 포스3
reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.
카잉 달력(6064번)
https://www.acmicpc.net/problem/6064
문제
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, x, y가 주어졌을 때 < x:y >이 몇 번째 해인지 구하는 문제
입력
첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T, 각 테스트 데이터는 한 줄로 구성, 각 줄에는 네 개의 정수 M, N, x와 y, < M:N >은 카잉 달력의 마지막 해
1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N
출력
출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 < x:y >가 k번째 해를 나타내는 것을 의미한다. 만일 < x:y >에 의해 표현되는 해가 없다면, 즉, < x:y >가 유효하지 않은 표현이면, -1을 출력한다.
풀이
- 날짜 계산(1476번, E S M)과 비슷한 문제
- 전체 경우의 수 MN = 1,600,000,000 가지라서 너무 많다.
- 모든 값에서 1을 빼면 나머지 값을 이용해 구할 수 있다. i : < i % M, i % N >
- x = 3이면 M으로 나눈 나머지 3이란 뜻이고 i x M + 3 이다. (M=5, N=7, i=0 -> 3, i=1 -> 8)
- 전체를 보지 않고 x=3 인것에서만 검색하면 N가지만 검색하면 됨.
- x를 이용해 모든 해를 고려하지 않고, i x M + x (i≥0)의 형태만 조사하면 된다. O(N)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t>0) {
int m = sc.nextInt();
int n = sc.nextInt();
int x = sc.nextInt();
int y = sc.nextInt();
x -= 1;
y -= 1;
boolean is = false;
for(int i=x; i<(n*m); i+=m) {
// m으로 나눈 나머지가 x인 모든 i를 볼 수 있음
if(i%n == y) {
System.out.println(i+1);
is = true;
break;
}
}
if(!is) {
System.out.println(-1);
}
t--;
}
}
}
-> 시간을 더 줄이기 위해선 BufferedReader 쓸 것
수 이어 쓰기 1 (1748번)
https://www.acmicpc.net/problem/1748
문제
1부터 N까지 수를 이어서 쓰면 새로운 하나의 수를 얻게 된다. (1 ≤ N ≤ 100,000,000)
1234567891011121314151617181920212223…
이 때, 새로운 수는 몇 자리 수일까?
입력
첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.
출력
첫째 줄에 새로운 수의 자릿수를 출력한다.
풀이
- 직접 만들어서 하면 복잡도 O(N), 시간이 오래 걸림
- 빠른 방법은 중복된 계산이 많단 걸 이용해 한 번에 처리
- 1~9 1자리 수라서 +1
- 10~99 2자리 수라서 +2
- 100~999 3자리 수라서 +3
- 총 N개의 수를 하나의 문자열로 만들기. O(N) x 10, 10은 수의 최대 자릿수를 의미한다.
- (9-1+1) x 1 + (99-10+1) x 2 + (356-10+1) x 3
- 이렇게 건너뛰면 최대 9번만 계산해주면 됨. O(logN)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long ans = 0;
for(int start=1, len=1; start<=n; start*=10, len++) {
int end = start*10-1;
if(end>n) {
end = n;
}
ans += (long)(end-start+1)*len;
}
System.out.println(ans);
}
}
1,2,3 더하기 (9095번)
https://www.acmicpc.net/problem/9095
문제
정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
풀이
- N중 for문 : N개 중에 일부를 선택해야 하는 경우 많이 사용, 재귀호출이나 비트마스크를 사용하면 더 간결하고 보기 쉬운 코드를 작성할 수 있어 사용할 일이 거의 없다.
- 최대 3 x 3 x … x 3 = 3^10 가지. 그렇게 큰 수가 아니라 다 구할 수 있음.
import java.util.*;
public class Main {
static int n;
static int ans = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i=0; i<t; i++) {
n = sc.nextInt();
ans = 0;
sum(0);
System.out.println(ans);
}
}
private static void sum(int i) {
if(i>n) return;
if(i==n) {
ans++;
return;
}
sum(i+1); //1더하기
sum(i+2); //2더하기
sum(i+3); //3더하기
}
}
-> n중 for문은 너무 길어서 다른 방법들을 찾아봤는데 dp로 푸는 방법도 있고 재귀를 이용한 풀이도 있고 다양했다. 해당 코드는 재귀로 푼 코드인데 아직 직관적으로 다가오진 않는다. 재귀 어려워…
댓글남기기