날짜 계산
- 준규가 사는 나라는 E S M 이라는 연도를 사용. - 1<=E<=15, 1<=S<=28, 1<=M<=19 - 1년 = 1 1 1 17년 = 2 17 17 - 2년 = 2 2 2 18년 = 3 18 18 - ... - 15년 = 15 15 15 20년 = 5 20 1 - 16년 = 1 16 16 21년 = 6 21 2 - E S M 이 주어졌을 때, 이게 몇 년인지 구하는 문제.
-
( E,S,M ) 조합의 수 152819 = 7980
-
i년 : e, s, m 의 조합
-
i+1년 : e+1, s+1, m+1
e는 15, s는 28, m은 19까지 -
e가 16, s가 29, m이 20이 되었을 때 1으로 바꿔줌.
//다른 풀이
-
1<=E<=15
-
모든 E, S, M에서 1을 빼면, 이 문제는 다음을 만족하는 가장 작은 자연수 Year을 찾는 문제
-
year mod 15 == E
-
year mod 28 == S
-
year mod 19 == M
이런식으로 year을 0부터 증가시키면서 위의 식을 검사해 구현하는 방법도 가능함. -
e,s,m을 나머지 연산을 이용해서 계산하면 됨.
-
i년 : i%15, i%28, i%17
-> 출력할 때 +1해서 출력하면 됨.
//중국인의 나머지 정리로도 풀이가 가능함.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int e = sc.nextInt()-1;
int s = sc.nextInt()-1;
int m = sc.nextInt()-1;
for(int i=0;;i++) {
if(i%15==e && i%28==s &&i%19==m) {
System.out.println(i+1);
break;
}
}
}
}
리모컨
- TV채널을 리모컨을 이용해 바꾸는 문제
- 버튼 : 0,1,2,3,4,5,6,7,8,9,+,-
- 일부 숫자 버튼이 고장남.
- 현재 보고 있는 채널 : 100
- 이동하려고 하는 채널 : N
- 이 때, 리모컨 버튼을 누르는 횟수를 최소로 하는 문제.
- 따라서 숫자 버튼을 누르고 그 다음 +나 -중 하나만 연속해서 눌러야함.
- 이동하려고 하는 채널 N(0<=N<=500,000)
- 숫자 버튼을 눌러서 이동하는 채널 C (O<=C<=1,000,000)
- 절대 하면 안되는 것 : 불필요한 값, 중복되는 값의 계산
- 최소값을 구하는 문제에서도 중요함.
1) 숫자버튼 -> +/-버튼
2) +/-버튼 둘 중에 하나만 누르면 됨
(+-) -> 원래 상태로 돌아오기 때문에. 중복되는 계산에 속함.
- N번 채널로 이동하는 것이 목표.
- 숫자 버튼을 몇번, 어떤 채널로 이동해야하는지는 알 수 없음.
- 알 수 없다는 정보 -> Brute force에서 매우 중요함.
-> 알 수 없다는 것이 brute force이기 때문에 모든 경우의 수를 해봄. - +/- 가 몇 번?
1) 채널 C를 정하고 고장난 버튼을 확인
2) 고장나지 않은 버튼을 이동해서 이동할 수 있는 채널 C를 만듬.
(재귀함수를 사용해야함)
-> 시간 복잡도가 같으면 구현하기 편한쪽으로 사용하는 것이 좋음.
- broken[i]->숫자 버튼 i가 고장났으면 true, 그렇지 않으면 false
- 목표 채널 n을 입력받고 고장난 버튼을 입력받음.
- 정답의 초기값을 설정 : 숫자 버튼을 안 누름.
- possible함수
채널 c로 이동이 가능하면 c에 숫자의 개수를 return
이동이 불가능하면 0을 리턴함.
import java.util.Scanner;
public class Main {
static boolean broken[] = new boolean[10]; //고장난 숫자 버튼 배열
static int possible(int a) {
if(a==0) {
if(broken[0]) //고장났으면 0을 리턴
return 0;
}else { //아니라면 1을 리턴
return 1;
}
int len=0;
while(a>0) {
if(broken[a%10]) { //계속해서 a를 10으로 나눈 나머지의 값을 구해서 고장났는지 확인
return 0;
}
len += 1;
//길이 하나씩 더해줌.
a /= 10; //a를 계속 10으로 나누면서 값을 구해가면서 길이를 구함
}
return len;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
for(int i=0;i<m;i++) {
int num = sc.nextInt();
broken[num]=true;
}
int res = n-100; //현재 채널이 100번 이므로 이동하려고 하는 채널에서 100을 빼줌
if(res < 0) {
res = -res; //값이 음수라면 절대값 취해줌.
}
for(int i=0;i<=1000000;i++) {
int a=i;
int len = possible(a);
if(len>0) {
int press = a-n;
if(press <0) {
press= -press;
}
if(res > len + press) {
res = len + press;
}
}
}
System.out.println(res);
}
}테트로미노
- 폴리오미노는 크기가 1x1인 정사각형을 여러 개 이어 붙여서 만든 도형이다.
- 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며 총 5가지가 있다.
- N X M 크기의 종이 위에 테트로미노를 하나 놓아서 놓인 칸에 쓰여 있는 수의 합을 최대로 하는 문제
- 4<=N , M<=500
- 모든 모양에 대해서 기준을 만들어 주어야 함. (왼쪽 맨위를 기준으로 잡아봄)
방법1) (i,j) : 테트로미노의 기준.
19가지 방법을 하나씩 만들어 보는 방식으로 구현.
-> 단점 : 실수를 찾기가 어려움.
방법2) (i,j) 기준을 정했으면 (i,j+1) (i,j+2)~~을 하나씩 써주는 것이 아니라 얼마만큼 변하는지를 새로운 블록에 넣어줌.
방법3) 블럭을 {"1111"},
{"11",
"11"} 이런식으로 테트리스 모양으로 만들어줌.
나는 방법1로 구현..
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n= sc.nextInt();
int m= sc.nextInt();
int arr[][]= new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
arr[i][j]=sc.nextInt();
}
}
int max=0;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(j+3<m) {
int tmp=arr[i][j] + arr[i][j+1] + arr[i][j+2] +arr[i][j+3];
if(max < tmp) max = tmp;
}
if(i+3<n) {
int tmp=arr[i][j] + arr[i+1][j] + arr[i+2][j] +arr[i+3][j];
if(max < tmp) max= tmp;
}
if(i+1<n && j+1<m) {
int tmp=arr[i][j] + arr[i+1][j] +arr[i][j+1] +arr[i+1][j+1];
if(max < tmp) max=tmp;
}
if(i+1<n && j+2<m) {
int tmp=arr[i][j]+arr[i+1][j]+arr[i+1][j+1]+arr[i+1][j+2];
if(max < tmp) max=tmp;
}
if(i+2<n && j+1<m) {
int tmp=arr[i][j]+arr[i+1][j]+arr[i][j+1]+arr[i+2][j];
if(max < tmp) max=tmp;
}
if(i+1<n && j+2<m) {
int tmp=arr[i][j]+arr[i][j+1]+arr[i][j+2]+arr[i+1][j+2];
if(max < tmp) max=tmp;
}
if(i+2<n && j-1<m) {
int tmp=arr[i][j]+arr[i+1][j]+arr[i+2][j]+arr[i+2][j-1];
if(max < tmp) max=tmp;
}
if(i-1<n && j+2<m) {
int tmp=arr[i][j]+arr[i][j+1]+arr[i][j+2]+arr[i-1][j+2];
if(max < tmp) max=tmp;
}
if(i+2<n && j+1<m) {
int tmp=arr[i][j]+arr[i+1][j]+arr[i+2][j]+arr[i+2][j+1];
if(max < tmp) max=tmp;
}
if(i+1<n && j+2<m) {
int tmp = arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j];
if(max < tmp) max=tmp;
}
if(i+2<n && j+1<m) {
int tmp = arr[i][j] + arr[i][j+1] + arr[i+1][j+1] + arr[i+2][j+1];
if(max < tmp) max=tmp;
}
if(i-1<n && j+2<m) {
int tmp = arr[i][j] + arr[i][j+1] + arr[i-1][j+1] + arr[i-1][j+2];
if(max < tmp) max=tmp;
}
if(i+2<n && j+1<m) {
int tmp = arr[i][j] + arr[i+1][j] + arr[i+1][j+1] + arr[i+2][j+1];
if(max < tmp) max=tmp;
}
if(i+1<n && j+2<m) {
int tmp = arr[i][j] + arr[i][j+1] + arr[i+1][j+1] + arr[i+1][j+2];
if(max < tmp) max=tmp;
}
if(i+2<n && j-1<m) {
int tmp = arr[i][j] + arr[i+1][j] + arr[i+1][j-1] + arr[i+2][j-1];
if(max < tmp) max=tmp;
}
if(j+2<m) {
int tmp = arr[i][j] + arr[i][j+1] + arr[i][j+2];
if(i-1>=0) {
int tmp2 = tmp + arr[i-1][j+1];
if(max < tmp2) max=tmp2;
}
if(i+1 <n) {
int tmp2 = tmp + arr[i+1][j+1];
if(max < tmp2) max = tmp2;
}
}
if(i+2<m) {
int tmp = arr[i][j] + arr[i][j+1] + arr[i][j+2];
if(j+1 <m) {
int tmp2 = tmp + arr[i+1][j+1];
if(max < tmp2) max=tmp2;
}
if(j-1 >=0) {
int tmp2 = tmp + arr[i+1][j-1];
if(max < tmp2) max = tmp2;
}
}
}
}
System.out.println(max);
}
}
열심히 코드 짰는데 런타임 에러난다^^;;;;;ㅠㅠ...
#back_end #developer #🐥