첫 코드포스 contest 참가

codeforces.com/contest/1485

Dashboard - Codeforces Round #701 (Div. 2) - Codeforces

Codeforces Round #701 (Div. 2) 에 참가했다. (2021년 2월 12일 밤 11시 50분 - 한국 시간)

6문제 중 2문제를 풀었고 1문제를 더 읽어봤다. ㅎㅎ

시간 안에 영어로 된 문제 3문제를 이해했다는 것에 의의를 둔다...!

 

A번 문제

codeforces.com/contest/1485/problem/A

Problem - A - Codeforces

입력으로 a와 b가 주어지고 a가 0이 될 때까지 수행해야하는 연산의 최솟값을 계산하는 문제

 

연산은 두 가지

어디서 본 느낌이다 했는데 백준의 숨바꼭질 문제랑 비슷한 것 같다...! 그래서 bfs를 사용하여 풀었다.

처음에는 시간초과가 나서 LinkedList의 removeFirst를 get메소드를 대신하여 사용하였다.

 

※ 코드

import java.util.*;
import java.io.*;

public class CF_1485A {

	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);
		ArrayList<int []> queue;
		int [] temp;
		int [] temp1;
		int ans=0;
		int i=0;
		
		for(int t=0;t<T;t++) {
			s=br.readLine();
			st=new StringTokenizer(s);
			temp=new int[3];
			
			temp[0]=Integer.parseInt(st.nextToken());
			temp[1]=Integer.parseInt(st.nextToken());
			temp[2]=0;
			
			queue=new ArrayList<int []>();
			queue.add(temp);
			i=0;
			while(i<queue.size()) {
				temp=queue.get(i);
				if(temp[0]==0) {
					ans=temp[2];
					break;
				}
				temp1=new int[3];
				temp1[0]=Math.floorDiv(temp[0],temp[1]);
				temp1[1]=temp[1];
				temp1[2]=temp[2]+1;
				queue.add(temp1);
				
				temp1=new int[3];
				temp1[0]=temp[0];
				temp1[1]=temp[1]+1;
				temp1[2]=temp[2]+1;
				queue.add(temp1);
				i++;
			}
			bw.write(ans+"\n");
		}
		bw.flush();
		bw.close();
	}

}

B번 문제

codeforces.com/contest/1485/problem/B

Problem - B - Codeforces

이 문제가 문제 이해하는 데 제일 오래 걸렸다....ㅎㅎ

대충 설명하자면 주어진 배열에서 l에서 r번째까지의 수 중 원래의 배열과 하나만 숫자가 다른 수열은 몇 개니? 이런 문제다 (단조 증가의 조건은 유지해야함)

문제의 포인트는 a[i]번째 자리에 들어갈 수 있는 수의 개수는 a[i+1]-a[i-1]과 관련이 있다는 것이다.

여기에 추가해서 양쪽 끝 배열만 더 체크해주면 끝난다.

 

런타임 에러가 많이 났는데 배열 크기를 잘못 지정해줘서 생긴 문제였따....ㅂr보....☆

 

※ 코드

import java.util.*;
import java.io.*;

public class CF_1485B {

	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();
		st=new StringTokenizer(s);
		
		int n=Integer.parseInt(st.nextToken());
		int q=Integer.parseInt(st.nextToken());
		int k=Integer.parseInt(st.nextToken());
		
		int [] arr=new int[101010];
		int [] dp=new int[101010];

		s=br.readLine();
		st=new StringTokenizer(s);
		
		for(int i=0;i<n;i++)
			arr[i]=Integer.parseInt(st.nextToken());
		
		for(int i=2;i<n;i++)
			dp[i]=dp[i-1]+(arr[i]-arr[i-2]-2);
		
		int a,b,ans,temp;
		
		for(int i=0;i<q;i++) {
			s=br.readLine();
			st=new StringTokenizer(s);
			
			a=Integer.parseInt(st.nextToken());
			b=Integer.parseInt(st.nextToken());
			if(a==b) {
				ans=k-1;
			}
			
			else {
				ans=(arr[a]-2)+(k-arr[b-2]-1);
				
				temp=dp[b-1]-dp[a];
				ans+=temp;
			}
			bw.write(ans+"\n");
		}
		
		bw.flush();
		bw.close();
	}

}