PS 시나브로

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

문제 요약 : 수를 조합하여 주어진 부호에 맞는 숫자 출력

JAVA

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

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

public class Main {
	
	static int[][] op;
	static int[] arr;
	static int n;
	static boolean chk;
    static StringBuilder sb = new StringBuilder();
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i,j,k;
		n = Integer.parseInt(br.readLine());
		op = new int[n][n];
		arr = new int[n+1];
		String str = br.readLine();
		k = 0;
		for(i=0;i<n;i++) {
			for(j=i;j<n;j++) {
				if(str.charAt(k)=='-') {
					op[i][j] = -1;
				}else if(str.charAt(k)=='0') {
					op[i][j] = 0;
				}else {
					op[i][j] = 1;
				}
				k++;
			}
		}
		chk = false;
		btr(0);
		System.out.println(sb);
	}
	
	static void btr(int k) {
		if(chk) return;
		if(k==n) {
			for(int i=1;i<=n;i++) sb.append((arr[i]-arr[i-1])+" ");
			chk = true;
			return;
		}
		int mx = 10;
		int mi = -10;
		for(int i=0;i<=k;i++) {
			if(op[i][k]==-1) {
				mx = Math.min(mx, arr[i]-arr[k]-1);
			}else if(op[i][k]==0) {
				mx = Math.min(mx, arr[i]-arr[k]);
				mi = Math.max(mi, arr[i]-arr[k]);
			}else {
				mi = Math.max(mi, arr[i]-arr[k]+1);
			}
		}
		for(int i=mi;i<=mx;i++) {
			arr[k+1] = arr[k] + i;
			btr(k+1);
		}
	}
}

숫자를 앞에서 부터 가능한 숫자를 구하여 가능한 모든 경우를 확인한다.

숫자의 범위가 -10 부터 10이므로 초기값을 최소 -10, 최대 10으로 설정 한 후

해당 순번의 부분합 부호를 확인하며 들어갈 수 있는 최소 또는 최대 값을 수정하며 탐색한다.

예제 )

4
-+0++++--+

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

문제 요약 : 주어진 마일리지로 들을 수 있는 과목의 최대 개수 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_12018.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,m,i,j,p,l,s;
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int[] arr = new int[n];
		for(i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			p = Integer.parseInt(st.nextToken());
			l = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			if(p>=l) {
				int[] sub = new int[p];
				for(j=0;j<p;j++) sub[j] = Integer.parseInt(st.nextToken());
				Arrays.sort(sub);
				arr[i] = sub[p-l];
			}else {
				arr[i] = 1;
			}
		}
		Arrays.sort(arr);
		s = 0;
		for(i=0;i<n;i++) {
			if(arr[i]>m) break;
			m -= arr[i];
			s++;
		}
		System.out.println(s);
	}
}

과목을 하나 하나 확인하며

해당 강의의 정원보다 수강을 신청한 인원이 적을 경우

해당 강의의 비용을 1로 한다.

해당 강의의 정원보다 수강을 신청한 사람이 같거나 클 경우

신청한 학생들이 넣은 마일리지를 정렬 하여 강의의 정원 수 번째로 큰수를 강의의 비용으로 한다.

위의 과정에서 나온 비용을 오름차순 정렬하여 마일리지로 해당 과목을 신청할 수 있는지 확인한다.

예제 )

5 76
5 4 
36 25 1 36 36
4 4
30 24 25 20
6 4
36 36 36 36 36 36
2 4
3 7
5 4
27 15 26 8 14

76 마일리지를 가지고 있었으므로 4 개의 강의를 수강신청 할 수 있다.

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

문제 요약 : 부분합 계산

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_11441.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 n,m,i,s,e;
		n = Integer.parseInt(br.readLine());
		int[] arr = new int[n+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(i=1;i<=n;i++) arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
		m = Integer.parseInt(br.readLine());
		while(m-->0) {
			st = new StringTokenizer(br.readLine());
			s = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			sb.append((arr[e]-arr[s-1])+"\n");
		}
		System.out.println(sb);
	}
}

주어진 수열을 1~n까지 부분합을 미리 계산 후

주어진 구간의 시작을 s 끝을 e라고 할 때

e의 부분합에서 s-1의 부분합을 빼준다.

예제 ) 

5

10 20 30 40 50

5

1 3

2 4

3 5

1 5

4 4

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

문제 요약 : 모든 팀의 팀원에게 펜을 줄 때 펜을 빌려야 할 회원 최소 수 계산

JAVA

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
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;
		n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		m = Integer.parseInt(st.nextToken());
		m *= Integer.parseInt(st.nextToken());
		Integer[] arr = new Integer[n];
		st = new StringTokenizer(br.readLine());
		for(i=0;i<n;i++) arr[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(arr,Collections.reverseOrder());
		for(i=0;i<n;i++) {
			m -= arr[i];
			if(m<=0) break;
		}
		System.out.println(i==n?"STRESS":(i+1));
	}
}

필요 한 펜의 수 : 팀의 수 * 팀원의 수

따라서 회원이 가지고 있는 펜의수를 내림차순 정렬하여

필요한 펜의 수를 충족하는지 확인하면 된다.

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

문제 요약 : 1번 팀과 2번 팀이 이기고 있던 시간 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_2852.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 t,ntime,time,t_a,t_b,s;
		boolean chk;
		s = time = t_a = t_b = 0;
		t = Integer.parseInt(br.readLine());
		while(t-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			chk = st.nextToken().equals("1")?true:false;
			String str = st.nextToken();
			ntime = (str.charAt(0)-'0')*600;
			ntime += (str.charAt(1)-'0')*60;
			ntime += (str.charAt(3)-'0')*10;
			ntime += str.charAt(4)-'0';
			if(s>0) t_a += ntime - time;
			if(s<0) t_b += ntime - time;
			s += chk?1:-1;
			time = ntime;
		}
		if(s>0) t_a += 2880 - time;
		if(s<0) t_b += 2880 - time;
		System.out.printf("%02d:%02d\n%02d:%02d\n",t_a/60,t_a%60,t_b/60,t_b%60);
	}
}

시간을 0으로 초기화 한 후

주어진 득점에 대한 시간을 초로 환산하고

특정 팀이 이기고 있을 경우 현재시간과 시간의 차이 만큼 더해주고

득점을 계산 한 후 시간을 현재시간으로 치환 시켜준 뒤

마지막에 48분의 경우 따로 득점은 없지만 특정 팀이 이기고 있을 경우 시간을 더해준다.

예제 )

3

1 01:10

2 21:10

2 31:30

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

문제 요약 : 주어진 연도 사이의 앨범 모두 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_12791.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[] year = {1967, 1969, 1970, 1971, 1972, 1973, 1973, 1974, 1975, 1976, 1977, 1977, 1979, 1980, 1983, 1984, 1987, 1993, 1995, 1997, 1999, 2002, 2003, 2013, 2016};
		String[] name = {"DavidBowie", "SpaceOddity", "TheManWhoSoldTheWorld", "HunkyDory", "TheRiseAndFallOfZiggyStardustAndTheSpidersFromMars", "AladdinSane", "PinUps", "DiamondDogs", "YoungAmericans", "StationToStation", "Low", "Heroes", "Lodger", "ScaryMonstersAndSuperCreeps", "LetsDance", "Tonight", "NeverLetMeDown", "BlackTieWhiteNoise", "1.Outside", "Earthling", "Hours", "Heathen", "Reality", "TheNextDay", "BlackStar"};
		int t,a,b,i,s;
		t = Integer.parseInt(br.readLine());
		while(t-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			s = 0;
			for(i=0;i<25;i++) if(year[i]>=a&&year[i]<=b) s++;
			sb.append(s+"\n");
			for(i=0;i<25;i++) if(year[i]>=a&&year[i]<=b) sb.append(year[i]+" "+name[i]+"\n");
		}
		System.out.println(sb);
	}
}

사전에 25개 앨범의 연도와 제목을 저장해 두고

25개의 앨범을 차례대로 확인하며 주어진 연도 사이에 해당하는지 확인하여 개수를 세고 출력한다.

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

문제 요약 : 숫자일 경우 문자로 문자일 경우 숫자로 변환

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_12778.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,k;
		t = Integer.parseInt(br.readLine());
		while(t-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			k = Integer.parseInt(st.nextToken());
			if(st.nextToken().equals("C")) {
				st = new StringTokenizer(br.readLine());
				while(k-->0) sb.append((st.nextToken().charAt(0)-'A'+1)+" ");
			}else {
				st = new StringTokenizer(br.readLine());
				while(k-->0) sb.append((char)(Integer.parseInt(st.nextToken())+64)+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}

아스키코드 값 65 = 'A' 이므로

숫자일 경우 해당 값에 64를 더해 아스키코드 문자로 바꿔준다.

문자일 경우 해당 아스키코드 값에서 A(65)에 해당하는 값을 빼고 1을 더해준다.

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

문제 요약 : 주어진 집합의 차집합 출력

JAVA

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
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 a,b,i,t;
		HashMap<Integer,Boolean> map = new HashMap<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(i=0;i<a;i++) map.put(Integer.parseInt(st.nextToken()),true);
		st = new StringTokenizer(br.readLine());
		for(i=0;i<b;i++) {
			t = Integer.parseInt(st.nextToken());
			if(map.containsKey(t)) map.remove(t);
		}
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int k:map.keySet()) arr.add(k);
        Collections.sort(arr);
        sb.append(arr.size()+"\n");
        if(arr.size()!=0) for(int k:arr) sb.append(k+" ");
        System.out.println(sb);
	}
}

HashMap을 통해 A의 원소를 전부 넣어 준 뒤

B의 원소를 하나하나 확인하며 HashMap에 해당 원소가 있다면 해당 맵을 지워준다.

그 뒤 HashMap에 남은 원소를 ArrayList에 넣어 준 뒤 정렬하여 출력한다.