PS 시나브로

문제 : https://www.acmicpc.net/problem/11444

문제 요약 : n 번째 피보나치수를 1000000007로 나눈 나머지 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_11444.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i,j,k;
		long n;
		long[][] narr = new long[2][2];
		long[][] tarr = new long[2][2];
		n = Long.parseLong(br.readLine());
		n--;
		narr[0][0] = narr[1][1] = 1;
		tarr[0][0] = tarr[0][1] = tarr[1][0] = 1;
		while(n>0) {
			if(n%2==1) {
				long[][] sarr = new long[2][2];
				for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) sarr[i][j] += narr[i][k]*tarr[k][j];
				for(i=0;i<2;i++) for(j=0;j<2;j++) narr[i][j] = sarr[i][j]%1000000007;
			}
			long[][] sarr = new long[2][2];
			for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) sarr[i][j] += tarr[i][k]*tarr[k][j];
			for(i=0;i<2;i++) for(j=0;j<2;j++) tarr[i][j] = sarr[i][j]%1000000007;
			n/=2;
		}
		System.out.println((narr[1][0]+narr[1][1])%1000000007);
		
	}
}

이 문제를 풀기 위해서는 위와 같은 식을 이용해 구해야 한다.

이때 n이 상당히 크므로 한번씩 계산하면 시간 초과가 난다.

초기에는 narr을 단위행렬(E), tarr을 {{1,1},{0,1}}로 초기화하고

sarr을 배열의 복사를 위해 사용한다.

이때 F_n+1값을 구하게 되므로 n에서 1을 빼고 다음과 같이 진행한다.

n이 0보다 클때까지

1. n을 2로 나눴을 때 나머지가 1 일 경우에는 narr에 tarr을 곱해주고 tarr을 거듭제곱해준다.

2. n을 2로 나눴을 때 나머지가 0 일 경우에는 tarr을 거듭제곱해준다.

3. n을 2로 나눠준다.

n이 0이 됐을 경우 (c+d) 값을 1000000007로 나눈 나머지를 출력하면 된다.

예제 ) n = 1000일 경우

n에서 1을 빼주고 위 과정을 진행한다.

문제 : https://www.acmicpc.net/problem/2003

문제 요약 : 부분 수열의 합이 M이 되는 경우의 수 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_2003.java

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 br = new BufferedReader(new InputStreamReader(System.in));
		int n,m,i,s,l,r,t;
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int[] arr = new int[n+1];
		st = new StringTokenizer(br.readLine());
		for(i=1;i<=n;i++) arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
		s = 0;
		l = 0;
		r = 1;
		while(true) {
			if(r>n) break;
			t = arr[r] - arr[l];
			if(t>=m) l++;
			if(t<=m) r++;
			if(t==m) s++;
		}
		System.out.println(s);
	}
}

해당 배열의 숫자가 모두 양수이므로 투포인터 방식으로 문제를 해결할 수 있다.

부분합을 미리 계산 후

l = 0, r = 1로 초기화 한 후

부분합이 원하는 값(m) 보다 크거나 같을 경우 l을 오른쪽으로 한 칸

부분합이 원하는 값(m) 보다 작거나 같을 경우 r을 오른쪽으로 한 칸

부분합이 원하는 값(m) 같을 경우 경우의 수를 1 증가시켜주며

r이 마지막 값을 본 경우에는 종료시켜준다.

- 단순하게 모든 경우의 수를 구한 코드

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 br = new BufferedReader(new InputStreamReader(System.in));
		int n,m,i,j,s;
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int[] arr = new int[n+1];
		st = new StringTokenizer(br.readLine());
		for(i=1;i<=n;i++) arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
		s = 0;
		for(i=0;i<n;i++) for(j=i+1;j<=n;j++) if(arr[j]-arr[i]==m) s++;
		System.out.println(s);
	}
}

위 방법은 배열의 값이 음수인 경우에도 적용될 수 있지만 시간복잡도가

투포인터[O(n)] 에서 모든 경우의수[O(n^2)]으로 증가하게 된다.

문제 : https://www.acmicpc.net/problem/1356

문제 요약 : 유진수 인지 아닌지 확인

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_1356.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int a,b,i,j,sz;
		String str = br.readLine();
		boolean chk = false;
		sz = str.length();
		for(i=0;i<sz-1;i++) {
			a = b = 1;
			for(j=0;j<=i;j++) a *= str.charAt(j)-'0';
			for(j=i+1;j<sz;j++) b *= str.charAt(j)-'0';
			if(a==b) {
				chk = true;
				break;
			}
		}
		System.out.println(chk?"YES":"NO");
	}
}

문자열을 두 부분으로 나누어 각 자릿수를 곱하여 비교한다.

문제 : https://www.acmicpc.net/problem/2546

문제 요약 : 두 과목의 평균 IQ를 올릴 수 있는 사람 수 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_2546.java

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 br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int t,i,n,m,s;
		long suma,sumb;
		t = Integer.parseInt(br.readLine());
		while(t-->0) {
			br.readLine();
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			long[] arra = new long[n];
			suma = sumb = 0;
			st = new StringTokenizer(br.readLine());
			for(i=0;i<n;i++) {
				arra[i] = Integer.parseInt(st.nextToken());
				suma += arra[i];
			}
			st = new StringTokenizer(br.readLine());
			for(i=0;i<m;i++) sumb += Integer.parseInt(st.nextToken());
			s = 0;
			for(i=0;i<n;i++) if(arra[i]*n<suma&&arra[i]*m>sumb) s++;
			sb.append(s+"\n");
		}
		System.out.println(sb);
	}
}

해당 학생의 IQ가

C언어 수강생의 평균 IQ 보다 작고

경제학 학생의 평균 IQ보다 큰

경우의 수를 출력해주면 된다.

이때 해당 과목의 평균은

평균 = 해당 과목의 총합 / 해당 과목의 수강생 수로 나타낼 수 있으며

int형의 경우 소수점 아래부분이 제거되므로

이항 시켜 곱셈으로 바꿔준다.

따라서

해당 학생의 IQ * C언어 수강생 수 > C언어 수강생의 총 IQ

해당학생의 IQ * 경제학 수강생 수 < 경제학 수강생의 총 IQ

의 경우의 수를 계산하면 된다.

문제 : https://www.acmicpc.net/problem/17404

문제 요약 : 모든 집을 칠하는 비용의 최솟값을 출력한다.

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_17404.java

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 br = new BufferedReader(new InputStreamReader(System.in));
		int n,i,t,m;
		n = Integer.parseInt(br.readLine());
		int[][] dp = new int[n][9];
		dp[0][0] = dp[0][1] = 1000000000;
		dp[0][3] = dp[0][5] = 1000000000;
		dp[0][7] = dp[0][8] = 1000000000;
		StringTokenizer st = new StringTokenizer(br.readLine());
		dp[0][6] = Integer.parseInt(st.nextToken());
		dp[0][4] = Integer.parseInt(st.nextToken());
		dp[0][2] = Integer.parseInt(st.nextToken());
		for(i=1;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			t = Integer.parseInt(st.nextToken());
			dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + t;
			dp[i][3] = Math.min(dp[i-1][4], dp[i-1][5]) + t;
			dp[i][6] = Math.min(dp[i-1][7], dp[i-1][8]) + t;
			t = Integer.parseInt(st.nextToken());
			dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + t;
			dp[i][4] = Math.min(dp[i-1][3], dp[i-1][5]) + t;
			dp[i][7] = Math.min(dp[i-1][6], dp[i-1][8]) + t;
			t = Integer.parseInt(st.nextToken());
			dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + t;
			dp[i][5] = Math.min(dp[i-1][3], dp[i-1][4]) + t;
			dp[i][8] = Math.min(dp[i-1][6], dp[i-1][7]) + t;
		}
		dp[n-1][2] = 1000000000;
		dp[n-1][4] = 1000000000;
		dp[n-1][6] = 1000000000;
		m = Integer.MAX_VALUE;
		for(i=0;i<9;i++) m = Math.min(m, dp[n-1][i]);
		System.out.println(m);
	}
}

배열을 [n][9] 크기로 만들어 

[n][0~2]는 첫 번째 집을 빨강으로 색칠로 했을 경우

[n][3~5]는 첫 번째 집을 초록으로 색칠로 했을 경우

[n][6~8]는 첫 번째 집을 파랑으로 색칠로 했을 경우

[i][0,3,6]은 i번째 집을 빨강으로 칠한 비용

[i][1,4,7]은 i번째 집을 초록으로 칠한 비용

[i][2,5,8]은 i번째 집을 파랑으로 칠한 비용

이때 해당 i번째 집을 색칠하는 비용은

i번째 집을 해당 색으로 색칠하는 최소비용은

그 이전의 해당색을 제외한 집을 색칠한 최소비용과 i번째 집을 해당 색으로 색칠하는 값의 합이다.

예를 들어 i번째 집을 빨강으로 칠하는 경우는

i번째 집을 빨강으로 칠하는 비용 + i-1번째 집을 파랑 혹은 초록으로 칠하는 비용 중 작은 값이다.

마지막으로

빨강으로 시작했을 경우 빨강으로 끝나는 경우 또는

초록으로 시작했을 경우 초록으로 끝나는 경우 또는

파랑으로 시작했을 경우 파랑으로 끝나는 경우

위 3가지 경우를 제외해야 하므로 해당 값을 비용의 최대값으로 수정 후

해당 마지막배열의 최솟값을 출력한다.

문제 : https://www.acmicpc.net/problem/20040

문제 요약 : 사이클이 형성된 라운드 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_20040.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int[] parent;
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n,m,i,a,b,x,y;
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		parent = new int[n];
		for(i=0;i<n;i++) parent[i] = i;
		for(i=1;i<=m;i++) {
			st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			a = find(x);
			b = find(y);
			if(a==b) {
				System.out.println(i);
				return;
			}
			union(x,y);
		}
		System.out.println("0");
	}
	
	static int find(int x) {
		if(parent[x]==x) return x;
		return find(parent[x]);
	}
	
	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if(x<y) {
			parent[y] = x;
		}else {
			parent[x] = y;
		}
	}
}

find 함수를 이용해 두 수의 부모가 같다면 사이클이 형성된 것이므로 해당 라운드를 출력한다.

그렇지 않을 경우 find 함수를 이용해 두 수의 부모를 구하고 큰 값의 부모를 작은 값으로 수정해준다.

문제 : https://www.acmicpc.net/problem/9252

문제 요약 : 두 문자열의 가장 긴 부분 수열 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_9252.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int asz,bsz,i,j,s;
		String stra,strb;
		stra = br.readLine();
		strb = br.readLine();
		asz = stra.length();
		bsz = strb.length();
		int[][] lcs = new int[asz+1][bsz+1];
		for(i=0;i<asz;i++) {
			for(j=0;j<bsz;j++) {
				if(stra.charAt(i)==strb.charAt(j)) {
					lcs[i+1][j+1] = lcs[i][j]+1;
				}else {
					lcs[i+1][j+1] = Math.max(lcs[i][j+1], lcs[i+1][j]);
				}
			}
		}
		s = lcs[asz][bsz];
		sb.append(s+"\n");
        Stack<Character> stack = new Stack<>();
        i = asz;
        j = bsz;
        while(i>0&&j>0) {
        	if(lcs[i-1][j]==lcs[i][j]) {
        		i--;
        		continue;
        	}
        	if(lcs[i][j-1]==lcs[i][j]) {
        		j--;
        		continue;
        	}
        	stack.add(stra.charAt(i-1));
        	i--;
        	j--;
        }
        if(!stack.isEmpty()) {
        	while(!stack.isEmpty()) sb.append(stack.pop());
        	sb.append("\n");
        }
        System.out.println(sb);
	}
}

길이가 a이고 b인 문자열이 있을 때

[a+1][b+1] 크기의 배열을 만들고 다음과 같이 위에서 아래로 왼쪽에서 오른쪽 방향으로 계산해준다.

a의 i번째 문자를 i+1번째 열, b의 j번째 문자를 j+1번째 행이라 할 때

i번째 문자와 j번째 문자가 같을 경우 [i-1][j-1]의 값에서 1을 더해준다.

i번째 문자와 j번째 문자가 다를 경우 [i-1][j] 혹은 [i][j-1]의 값 중 큰 값을 가져온다.

그 결과 오른쪽 아래의 행렬의 값이 두 문자열의 최장 부분 수열 길이가 되며

해당하는 문자열을 구하는 방법은 오른쪽 아래에서 시작하며

왼쪽이나 위쪽값이 해당 값과 같으면 해당 칸으로 이동한다.

왼쪽이나 위쪽값이 해당 값과 다를 경우 대각선으로 한 칸 이동하며 스택에 해당 값에 해당하는 문자열을 추가한다.

최종적으로 스택에 있는 문자열을 출력한다.

예제 ) 

ACAYKP
CAPCAK

문제 : https://www.acmicpc.net/problem/2467

문제 요약 : 두 수를 합하여 0에 가장 가깝게 하는 두 수 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_2467.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n,i,l,r,m,t,tl,tr;
		n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(i=0;i<n;i++) arr[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(arr);
		tl = l = 0;
		tr = r = n-1;
		m = Integer.MAX_VALUE;
		while(l<r) {
			t = arr[r]+arr[l];
			if(Math.abs(t)<m) {
				m = Math.abs(t);
				tl = l;
				tr = r;
			}
			if(t==0) break;
			if(t>0) r--;
			if(t<0) l++;
		}
		System.out.println(arr[tl]+" "+arr[tr]);
	}
}

용액의 특성 값을 오름차순 정렬한 뒤

왼쪽 끝과 오른쪽 끝에 포인터를 두고 두 값의 합을 확인한다.

합이 0일 경우 while문을 종료한다.

합이 양수 일경우 오른쪽 포인터를 한 칸 왼쪽으로 옮겨준다.

합이 음수 일경우 왼쪽 포인터를 한 칸 오른쪽으로 옮겨준다.

이 과정을 왼쪽포인터가 오른쪽 포인터보다 작을 때까지 반복해준다.

과정 중 두수 합의 절대값이 현재까지의 차이보다 작을 경우 위치를 기록해 놓는다.

과정 완료 후 저장해둔 포인터 위치에 해당하는 배열 값을 출력한다.