코드포스 Codeforces Round #702 (Div. 3)

codeforces.com/contest/1490

Dashboard - Codeforces Round #702 (Div. 3) - Codeforces

날짜가 좀 지나서 언제였는지는 기억이 안 나는데 어쨌든 후기!

 

Div.2만 계속 열려서 아쉬웠는데 처음으로 Div.3 대회에 참여할 수 있었다. 확실히 Div.2보다는 쉬웠던 것 같다.(그렇다고 많이 푼 건 아니지만...ㅎㅎ)

7문제 중 3문제를 풀었고 2문제를 더 읽어보았다.

(A, B, C 총 세 문제 풀었다. C 푸는 데 오래 걸려서 D는 손댔다가 시간이 다 돼서 그냥 포기했다.ㅎㅎ)

 

A번 문제

codeforces.com/contest/1490/problem/A

Problem - A - Codeforces

주어진 배열이 dense array가 되기 위해서 최소 몇 개의 수가 추가되어야 하는지 구하는 문제이다.

array가 dense 하다는 것은 배열의 연속된 두 숫자가 있을 때 둘 중 큰 숫자가 작은 숫자의 두 배를 넘지 않는다는 얘기이다. (두 배까지 가능)

 

풀이 방법은 배열을 입력받고 앞에서부터 쭉 훑으면서 두 숫자가 dense array의 규칙에 어긋난다면 min(혹은 max) 값을 업데이트하면서 몇 개의 숫자가 추가되어야 하는지 카운트해주면 된다.

import java.io.*;
import java.util.*;
import java.math.*;
 
public class Main {
	static int max(int a,int b) {
		if(a>=b) return a;
		else return b;
	}
	static int min(int a,int b) {
		if(a<=b) return a;
		else return b;
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		String s=br.readLine();
		int T=Integer.parseInt(s);
		
		int n,cnt,min,max;
		int [] arr;
		
		for(int t=0;t<T;t++) {
			s=br.readLine();
			n=Integer.parseInt(s);
			
			arr=new int[n];
			cnt=0;
			
			s=br.readLine();
			st=new StringTokenizer(s);
			for(int i=0;i<n;i++)
				arr[i]=Integer.parseInt(st.nextToken());
			
			for(int i=0;i<n-1;i++) {
				max=max(arr[i],arr[i+1]);
				min=min(arr[i],arr[i+1]);
				if(max<=2*min) continue;
				while(max>2*min) {//숫자 추가
					min*=2;
					cnt++;
				}
			}
			bw.write(cnt+"\n");
		}
		bw.flush();
		bw.close();
	}
 
}

 

 

B번 문제

codeforces.com/contest/1490/problem/B

Problem - B - Codeforces

 

 

크기 n의 배열이 주어졌을 때, 각 숫자를 3으로 나누었을 때의 나머지가 0인 수의 개수 == 1인 수의 개수 == 2인 수의 개수가 같도록 숫자를 수정해야한다. 이 때 수정하는 횟수의 최솟값을 구하면 된다. 여기서 숫자를 수정한다는 것의 의미는 배열의 원소 중에 하나의 크기를 1 증가시킨다는 이야기이다.

 

일단 배열의 원소를 모두 입력받고 3으로 나누었을 때 0이 되는 수의 개수, 1이 되는 수의 개수, 2가 되는 수의 개수를 구해준다. 그리고 반복문을 돌면서 하나씩 업데이트 해주면 된다.

import java.io.*;
import java.util.*;
public class Main {
	static int min(int c0,int c1,int c2) {
		if(c0<=c1&&c0<=c2) return 0; //c0가 가장 작을 경우 0 return
		else if(c1<=c0&&c1<=c2) return 1; //c1이 가장 작을 경우 1 return
		else return 2; //c2가 가장 작을 경우 2 return
	}
	static int max(int c0,int c1,int c2) {
		if(c0>=c1&&c0>=c2) return 0; //c0가 가장 클 경우 0 return
		else if(c1>=1&&c1>=c2) return 1; //c1이 가장 클 경우 1 return
		else return 2;//c2가 가장 클 경우 2 return
	}
 
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		String s=br.readLine();
		int T=Integer.parseInt(s);
		
		int n,c0,c1,c2,cnt,min,max,a,b,c;
		int [] arr;
		
		for(int t=0;t<T;t++) {
			s=br.readLine();
			n=Integer.parseInt(s);
			
			arr=new int[n];
			
			s=br.readLine();
			st=new StringTokenizer(s);
			
			c0=0;c1=0;c2=0;
			
			for(int i=0;i<n;i++) {
				arr[i]=Integer.parseInt(st.nextToken());
				if(arr[i]%3==0) c0++;
				else if(arr[i]%3==1) c1++;
				else c2++;
			}
			cnt=0;
			
			while(true) {
				if(c0==c1&&c1==c2) break;
				a=c0-c1;
				b=c1-c2;
				c=c2-c0;
				
				max=max(a,b,c);
				
				if(max==0) {
					if((c0+c1)%2==0) {
						cnt+=a/2;
						c0=(c0+c1)/2;
						c1=c0;
					}
					else {
						c0=(c0+c1)/2;
						c1=c0+1;
						cnt+=a/2+1;
					}
				}
				else if(max==1) {
					if((c1+c2)%2==0) {
						cnt+=b/2;
						c1=(c1+c2)/2;
						c2=c1;
					}
					else {
						c1=(c1+c2)/2;
						c2=c1+1;
						cnt+=b/2+1;
					}
				}
				else {
					if((c2+c0)%2==0) {
						cnt+=c/2;
						c2=(c2+c0)/2;
						c0=c2;
					}
					else {
						c2=(c0+c2)/2;
						c0=c2+1;
						cnt+=c/2+1;
					}
				}
			}
			bw.write(cnt+"\n");
		}
		bw.flush();
		bw.close();
	}
 
}

C번 문제

codeforces.com/contest/1490/problem/C

Problem - C - Codeforces

숫자 x가 주어지면 이 수를 두 수의 세제곱수의 합으로 표현할 수 있는지 여부를 출력하면 되는 문제이다.

이중반복문을 돌리면 쉽게 풀 수 있는 문제이지만 x의 범위가 크기 때문에 이중반복문의 범위를 정하는 것이 중요한 문제이다. 

 

먼저 x의 최댓값이 10의 12승이기 때문에 10의 4승까지의 세제곱수를 미리 배열에 저장해둔다.

 

그 뒤 x의 값을 받고 x의 세제곱근을 구해서 그 범위까지 바깥쪽 반복문을 돌려준다. 그리고 안쪽 반복문은 세제곱근에서 출발하여 바깥쪽 반복문의 index까지 돌려준다. (이렇게 안 하면 시간초과 난다....!)

import java.io.*;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		
		String s=br.readLine();
		int T=Integer.parseInt(s);
		
		long x;
		
		long [] arr=new long[10101];
		
		for(int i=1;i<=10000;i++) {
			arr[i]=(long)i*(long)i*(long)i;
		}
		
		boolean ck=false;
		
		long temp=arr[10000]+1;
		
		int cbrtx;
		
		for(int t=0;t<T;t++) {
			s=br.readLine();
			x=Long.parseLong(s);
			cbrtx=(int) Math.cbrt(x);
			ck=false;
			for(int i=1;i<=cbrtx;i++) {
				if(ck) break;
				for(int j=cbrtx;j>=i;j--) {
					temp=arr[i]+arr[j];
					if(temp<x) break;
					if(temp==x) {
						ck=true;
						break;
					}
				}
			}
		
			if(ck) bw.write("YES\n");
			else bw.write("NO\n");
		}
		bw.flush();
		bw.close();
	}
 
}