꼬마 정민이는 이제 A + B 정도는 쉽게 계산할 수 있다. 이제 A + B + C를 계산할 차례이다!
입력
첫 번째 줄에 A, B, C (1 ≤ A, B, C ≤ 10^12)이 공백을 사이에 두고 주어진다.
출력
A+B+C의 값을 출력한다.
코드
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));
StringTokenizer st = new StringTokenizer(br.readLine());
long sum = 0;
for (int i = 0; i < 3; i++) {
sum += Long.parseLong(st.nextToken());
}
System.out.println(sum);
}
}
러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.
이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다.
가스는 모스크바에서 자그레브로 흐른다. 가스는 블록을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블록으로, 아래 예시처럼 두 방향 (수직, 수평)으로 흘러야 한다.
파이프 라인의 설계를 마친 후 두 사람은 잠시 저녁을 먹으러 갔다. 그 사이 해커가 침임해 블록 하나를 지웠다. 지운 블록은 빈 칸이 되어있다.
해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블록이 있었는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 유럽의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 25)
다음 R개 줄에는 C개 글자가 주어지며, 다음과 같은 글자로 이루어져 있다.
빈칸을 나타내는 '.'
블록을 나타내는 '|'(아스키 124), '-','+','1','2','3','4'
모스크바의 위치를 나타내는 'M'과 자그레브를 나타내는 'Z'. 두 글자는 한 번만 주어진다.
항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어진다, 또, 모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다. 또, 불필요한 블록이 존재하지 않는다. 즉, 없어진 블록을 추가하면, 모든 블록에 가스가 흐르게 된다.
입력
첫째 줄에 유럽의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 25)
다음 R개 줄에는 C개 글자가 주어지며, 다음과 같은 글자로 이루어져 있다.
빈칸을 나타내는 '.'
블록을 나타내는 '|'(아스키 124), '-','+','1','2','3','4'
모스크바의 위치를 나타내는 'M'과 자그레브를 나타내는 'Z'. 두 글자는 한 번만 주어진다.
항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어진다, 또, 모스크바와 자그레브가 하나의 블록과 인접해 있는 입력만 주어진다. 또, 불필요한 블록이 존재하지 않는다. 즉, 없어진 블록을 추가하면, 모든 블록에 가스가 흐르게 된다.
출력
지워진 블록의 행과 열 위치를 출력하고, 어떤 블록이었는지를 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class JUN2931 {
static int R, C, dir, M[];
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static char map[][];
/*
* '|' 세로 블럭
* '-' 가로 블럭
* '+' 십자 블럭
* '1' 오 아 블럭
* '2' 위 오 블럭
* '3' 왼 위 블럭
* '4' 왼 아 블럭
* */
static char[] pipes = {'|','-','+','1','2','3','4'};
// 들어오는 방향에 따라 설치할 수 있는 파이트 종류
static char[][] pipes_case = {
{'|', '+', '4', '1'},
{'+', '|', '3', '2'},
{'2', '1', '-', '+'},
{'3', '4', '+', '-'}
};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st= new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
M = new int[2]; //모스크바 위치
for (int i = 0; i < R; i++) {
map[i] = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
if(map[i][j] == 'M'){
M[0] = i;
M[1] = j;
}
}
}
dir = -1;
//모스크바에서 출발 할 수 있는지 확인
for(int i = 0; i < 4; i++){
int tx = M[0] + dx[i];
int ty = M[1] + dy[i];
if(tx < 0 || tx >= R || ty < 0 || ty >= C) continue;
if(map[tx][ty]!='.') dir = i; // 모스크바와 연결된 가스관이 있으면 방향 저장
}
find_blank(M[0], M[1], dir);
}
// 중간에 끊어진 곳을 찾기
static void find_blank(int x, int y, int d){
int nx = x + dx[d];
int ny = y + dy[d];
//if(map[nx][ny] == '.') find_pip();
switch (map[nx][ny]){
case '.':
find_pipe(nx, ny, d);
break;
case '1':
if(d == 2){
d = 1;
} else{
d = 3;
}
find_blank(nx, ny, d);
break;
case '2':
if(d == 2){
d = 0;
} else{
d = 3;
}
find_blank(nx, ny, d);
break;
case '3':
if(d == 3){
d = 0;
} else{
d = 2;
}
find_blank(nx, ny, d);
break;
case '4':
if(d == 3){
d = 1;
} else{
d = 2;
}
find_blank(nx, ny, d);
break;
default:
find_blank(nx, ny, d);
}
}
// 빈곳에 들어가야하는 파이프 찾기
static void find_pipe(int x, int y, int d){
int undir = 0;
if(d == 0){
undir = 1;
} else if(d == 1){
undir = 0;
} else if(d == 2){
undir = 3;
} else if(d == 3){
undir = 2;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < 4; i++) {
if(i == undir) continue;
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= R || ny < 0 || ny >= C || map[nx][ny] == '.' || map[nx][ny] == 'Z') continue;
for (int j = 0; j < 4; j++) {
if(pipes_case[i][j] == map[nx][ny]){
q.offer(i);
}
}
}
x++;
y++;
if(q.size()>1){
System.out.println(x+" "+y+" "+pipes_case[d][undir]);
}else{
System.out.println(x+" "+y+" "+pipes_case[d][q.poll()]);
}
}
}
백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.
백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
아래 그림은 6개의 구역이 있는 것이고, 인접한 구역은 선으로 연결되어 있다.
입력
첫째 줄에 구역의 개수 N이 주어진다. 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다. 인구는 공백으로 구분되어져 있다.
셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다.
구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접하다. 인접한 구역이 없을 수도 있다.
출력
첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다. 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.
제한
2 ≤ N ≤ 10
1 ≤ 구역의 인구 수 ≤ 100
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N;
static int[] people;
static List<ArrayList<Integer>> graph;
static boolean visited[];
static boolean selected[];
static int re = Integer.MAX_VALUE;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
re = Integer.MAX_VALUE; // 결과
people = new int[N]; // 인구 수
selected = new boolean[N]; // 부분집합 용
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
people[i] = Integer.parseInt(st.nextToken()); // 지역구 별 인구 입력
}
graph = new ArrayList<>();
for (int i = 0; i < N; i++) {
graph.add(new ArrayList<Integer>()); // 준비
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int cnt = Integer.parseInt(st.nextToken()); // 인접 구역 수
for (int j = 0; j < cnt; j++) {
int next = Integer.parseInt(st.nextToken());
graph.get(i).add(next-1); //인덱스는 0부터 시작하니까
}
}
divide(0);
if(re == Integer.MAX_VALUE) re = -1;
System.out.println(re);
}
/* 부분 집합
* 지역구가 1개이면 안됨
* 나눌 지역들이 각각 연결 되어 있어야 함.(끊기면 안됨)
* */
private static void divide(int cnt) {
if(cnt == N) {
List<Integer> aList = new ArrayList<>(); // 1 지역구
List<Integer> bList = new ArrayList<>(); // 2 지역구
for (int i = 0; i < N; i++) { // 선택한 애들은 a, 아닌 지역구는 b
if(selected[i]) aList.add(i);
else bList.add(i);
}
// 한 쪽이 한 개도 없으면 X
if(aList.size() == 0 || bList.size() == 0) return;
//두 구역이 나눠저있는지 체크
if(check(aList) && check(bList)) {
getPeople();
}
return;
}
selected[cnt] = true;
divide(cnt+1);
selected[cnt] = false;
divide(cnt+1);
}
/*
* 지역구가 이어져 있는지 체크
* */
private static boolean check(List<Integer> list) {
Queue<Integer> q = new LinkedList<>();
visited = new boolean[N];
visited[list.get(0)] = true;
q.offer(list.get(0));
int cnt = 1;
while(!q.isEmpty()) {
int cur = q.poll();
for (int i = 0; i < graph.get(cur).size(); i++) {
int y = graph.get(cur).get(i);
if(list.contains(y) && !visited[y]) {
q.offer(y);
visited[y] = true;
cnt++;
}
}
}
if(cnt == list.size()) return true;
else return false;
}
private static void getPeople() {
int apeople = 0, bpeople = 0;
for(int i = 0; i < N; i++) {
if(selected[i]) apeople+=people[i];
else bpeople += people[i];
}
int sub = Math.abs(apeople-bpeople);
re = Math.min(re, sub);
}
}
워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자.
두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다.
편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n ≥ m이라고 가정해도 무리가 없다. n<m이면 어차피 P는 T중간에 나타날 수 없기 때문이다. 또, T의 i번째 문자를 T[i]라고 표현하도록 하자. 그러면 물론, P의 i번째 문자는 P[i]라고 표현된다.
1 2 3 4 5 6 7 8 9 …
T : [ A B C D A B C D A B D E ]
| | | | | | X
P : [ A B C D A B D ]
1 2 3 4 5 6 7
문자열 P가 문자열 T 중간에 나타난다는 것, 즉 문자열 P가 문자열 T와 매칭을 이룬다는 것이 어떤 것인지 위와 아래의 두 예를 통해 알아보자. 위의 예에서 P는, T의 1번 문자에서 시작하는 매칭에 실패했다. T의 7번 문자 T[7]과, P의 7번 문자 P[7]이 서로 다르기 때문이다.
그러나 아래의 예에서 P는, T의 5번 문자에서 시작하는 매칭에 성공했다. T의 5～11번 문자와 P의 1～7번 문자가 서로 하나씩 대응되기 때문이다.
1 2 3 4 5 6 7 8 9 …
T : [ A B C D A B C D A B D E ]
| | | | | | |
P : [ A B C D A B D ]
1 2 3 4 5 6 7
가장 단순한 방법으로, 존재하는 모든 매칭을 확인한다면, 시간복잡도가 어떻게 될까? T의 1번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 1～m번 문자와 P의 1～m번 문자를 비교한다면 최대 m번의 연산이 필요하다. 이 비교들이 끝난 후, T의 2번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 2～m+1번 문자와 P의 1～m번 문자를 비교한다면 다시 최대 m번의 연산이 수행된다. 매칭은 T의 n-m+1번 문자에서까지 시작할 수 있으므로, 이러한 방식으로 진행한다면 O( (n-m+1) × m ) = O(nm) 의 시간복잡도를 갖는 알고리즘이 된다.
더 좋은 방법은 없을까? 물론 있다. 위에 제시된 예에서, T[7] ≠ P[7] 이므로 T의 1번 문자에서 시작하는 매칭이 실패임을 알게 된 순간으로 돌아가자. 이때 우리는 매칭이 실패라는 사실에서, T[7] ≠ P[7] 라는 정보만을 얻은 것이 아니다. 오히려 i=1…6에 대해 T[i] = P[i] 라고 하는 귀중한 정보를 얻지 않았는가? 이 정보를 십분 활용하면, O(n)의 시간복잡도 내에 문자열 매칭 문제를 풀어내는 알고리즘을 설계할 수 있다.
P 내부에 존재하는 문자열의 반복에 주목하자. P에서 1, 2번 문자 A, B는 5, 6번 문자로 반복되어 나타난다. 또, T의 1번 문자에서 시작하는 매칭이 7번 문자에서야 실패했으므로 T의 5, 6번 문자도 A, B이다.
따라서 T의 1번 문자에서 시작하는 매칭이 실패한 이후, 그 다음으로 가능한 매칭은 T의 5번 문자에서 시작하는 매칭임을 알 수 있다! 더불어, T의 5～6번 문자는 P의 1～2번 문자와 비교하지 않아도, 서로 같다는 것을 이미 알고 있다! 그러므로 이제는 T의 7번 문자와 P의 3번 문자부터 비교해 나가면 된다.
이제 이 방법을 일반화 해 보자. T의 i번 문자에서 시작하는 매칭을 검사하던 중 T[i+j-1] ≠ P[j]임을 발견했다고 하자. 이렇게 P의 j번 문자에서 매칭이 실패한 경우, P[1…k] = P[j-k…j-1]을 만족하는 최대의 k(≠j-1)에 대해 T의 i+j-1번 문자와 P의 k+1번 문자부터 비교를 계속해 나가면 된다.
이 최대의 k를 j에 대한 함수라고 생각하고, 1～m까지의 각 j값에 대해 최대의 k를 미리 계산해 놓으면 편리할 것이다. 이를 전처리 과정이라고 부르며, O(m)에 완료할 수 있다.
이러한 원리를 이용하여, T와 P가 주어졌을 때, 문자열 매칭 문제를 해결하는 프로그램을 작성하시오.
입 출 력
첫째 줄에 문자열 T가, 둘째 줄에 문자열 P가 주어진다. T와 P의 길이 n, m은 1이상 100만 이하이고, 알파벳 대소문자와 공백으로만 이루어져 있다.
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
// KMP 알고리즘(Knuth–Morris–Pratt Algorithm)
// O(N+M)
public class JUN1786 {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
char[] text = in.readLine().toCharArray();
char[] pattern = in.readLine().toCharArray();
int tLength = text.length, pLength = pattern.length;
int[] pi = new int[pLength];
for(int i=1, j=0; i<pLength; i++){
while(j > 0 && pattern[i] != pattern[j]) j = pi[j-1];
if(pattern[i] == pattern[j]) pi[i] = ++j;
else pi[i] = 0;
}
int cnt = 0;
ArrayList<Integer> list = new ArrayList<Integer>();
// i : 텍스트 포인터 , j: 패턴 포인터
for(int i=0,j=0; i<tLength; ++i) {
while(j>0 && text[i] != pattern[j]) j = pi[j-1];
if(text[i] == pattern[j]) { //두 글자 일치
if(j == pLength-1) { // j가 패턴의 마지막 인덱스라면
cnt++; // 카운트 증가
list.add(i-j+1);
j=pi[j];
}else {
j++;
}
}
}
StringBuilder sb = new StringBuilder();
sb.append(cnt).append("\n");
//System.out.println(cnt);
if(cnt>0) {
//System.out.println(list);
for(int i : list){
sb.append(i).append(" ");
}
}
System.out.println(sb);
}
}
풀이
문자열 비교 알고리즘 중 하나인
KMP 알고리즘
으로 한 풀이입니다.
KMP (Knuth - Morris - Pratt) Algorithm
- 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행 - 시간 복잡도 : O(M+N)
상근이는 2차원 평면 위에서 움직일 수 있는 거북이 로봇을 하나 가지고 있다. 거북이 로봇에게 내릴 수 있는 명령은 다음과 같이 네가지가 있다.
F: 한 눈금 앞으로
B: 한 눈금 뒤로
L: 왼쪽으로 90도 회전
R: 오른쪽으로 90도 회전
L과 R명령을 내렸을 때, 로봇은 이동하지 않고, 방향만 바꾼다. 명령을 나열한 것을 거북이 로봇의 컨트롤 프로그램이라고 한다.
상근이는 자신의 컨트롤 프로그램으로 거북이가 이동한 영역을 계산해보려고 한다. 거북이는 항상 x축과 y축에 평행한 방향으로만 이동한다. 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형의 넓이를 구하는 프로그램을 작성하시오. 단, 직사각형의 모든 변은 x축이나 y축에 평행이어야 한다.
아래 그림에서 거북이는 가장 처음에 (0, 0)에 있고, 북쪽을 쳐다보고 있다. 컨트롤 프로그램이 FLFRFLBRBLB인 경우에 거북이는 아래와 같이 움직인다. 회색으로 빗금친 부분이 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형이다. 넓이는 4가 된다.
거북이가 지나간 영역이 직사각형을 만들지 않는 경우도 있다. 예를 들어, FFLLFF인 경우에 거북이는 y축의 위로만 지나다닌다. 이 경우에 거북이가 지나간 영역을 모두 포함하는 직사각형은 선분이고, 선분은 한 변이 0인 직사각형으로 생각할 수 있다. 따라서, 선분의 경우에 넓이는 0이 된다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 있고, 길이는 500을 넘지 않는다.
출력
각 테스트 케이스에 대해서, 거북이가 이동한 영역을 모두 포함하는 가장 작은 직사각형의 넓이를 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class JUN8911 {
/* 거북이
F : 한 눈금 앞으로
B : 한 눈금 뒤로
L : 왼쪽으로 90도 회전(전진 X)
R : 오른쪽으로 90도 회전(전진 X)
다 이동한 후에 가장 왼쪽, 가장 오른쪽 차가 가로 길이
가장 상단, 가장 하단의 차가 세로 길이니까
그 둘을 곱한다
* */
static int[][] map;
static int top, bottom, left, right, d;
static int hight, width; // 가로 세로
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine()); // 거북이 조작 횟수
String[] commands = new String[N];
for(int i = 0; i < N; i++){
top = 0;
bottom = 0;
left = 0;
right = 0;
d = 0; // 0 : 위, 1: 왼쪽, 2 : 밑, 3 : 오른쪽
hight = width = 0;
commands[i] = br.readLine();
tuttle(commands[i]);
sb.append(countArea()).append("\n");
}
System.out.println(sb);
}
// 거북이가 움직인다.
public static void tuttle(String c){
char[] command = c.toCharArray();
for(int i = 0; i < command.length; i++){
char temp = command[i];
if(temp == 'F' || temp == 'B'){
// 명령어가 F와 B 일때만 움직인다
move(command[i]);
} else if(temp == 'L' || temp == 'R'){
// 명령어가 L 과 R 일때는 방향만 바꿔준다.
changeD(command[i]);
}
}
}
// 직사각형 크기 구하기
public static int countArea(){
return (Math.abs(top-bottom)) * (Math.abs(left-right));
}
// 방향 바꿔주기
public static void changeD(char c){
if(c == 'L'){
d++;
} else{
d--;
}
// 0 : 위, 1: 왼쪽, 2 : 밑, 3 : 오른쪽 범위 넘어가면 수정 해주기
if(d == 4){
d = 0;
} else if(d == -1){
d = 3;
}
}
public static void move(char c){
switch (d){
case 0: // 위 보고 있음
if(c == 'F'){
hight++;
top = Math.max(top, hight);
} else{
hight--;
bottom = Math.min(bottom, hight);
}
break;
case 1: // 왼쪽 보고 있음
if(c == 'F'){
width++;
left = Math.max(left, width);
} else{
width--;
right = Math.min(right, width);
}
break;
case 2: // 밑에 보고 있음
if(c == 'F'){
hight--;
bottom = Math.min(bottom, hight);
} else{
hight++;
top = Math.max(top, hight);
}
break;
case 3: // 오른쪽 보고 있음
if(c == 'F'){
width--;
right = Math.min(right, width);
} else{
width++;
left = Math.max(left, width);
}
break;
}
}
}
풀이
거북이 로봇은 명령을 받아 움직인다.
명령어는 F, B, L, R 이 있다.
그 움직임이 멈춘 후 그 범위를 포함하는
직사각형의 넓이를 구하는게 이 문제이다.
직사각형의 넓이를 구하는 공식은 다들 아시다시피
사각형의 넓이 = 너비 x 높이
그렇죠?
너비는 어떻게 구하죠?
가장 맨 왼쪽부터, 가장 맨 오른쪽까지의 거리겠죠?
높이는 어떻게 구하죠?
가장 위에서, 가장 아래까지의 거리겠죠?
그러면 우리에게 필요한건,
가장 위, 가장 아래, 가장 왼쪽, 가장 오른쪽의 값이 겠죠?
뭘 구해야 할지 알았으니 시작해봅시다.
1. 거북이 로봇을 명령에 따라 움직인다.
뭐 움직이게 하면 다 끝이긴 합니다.
움직임은 크게
1) 전진(F) 과 후진(B)
2) 방향 전환(왼 : L, 오 : R)
입니다.
1) 전진과 후진
public static void move(char c){
switch (d){
case 0: // 위 보고 있음
if(c == 'F'){
hight++;
top = Math.max(top, hight);
} else{
hight--;
bottom = Math.min(bottom, hight);
}
break;
case 1: // 왼쪽 보고 있음
if(c == 'F'){
width++;
left = Math.max(left, width);
} else{
width--;
right = Math.min(right, width);
}
break;
case 2: // 밑에 보고 있음
if(c == 'F'){
hight--;
bottom = Math.min(bottom, hight);
} else{
hight++;
top = Math.max(top, hight);
}
break;
case 3: // 오른쪽 보고 있음
if(c == 'F'){
width--;
right = Math.min(right, width);
} else{
width++;
left = Math.max(left, width);
}
break;
}
}
눈치가 빠른 학생들은 선생님의 초콜릿을 훔쳐 먹었다! 이를 알아챈 선생님은 포스트잇에 현재 초콜릿의 남은 개수를 적어 놓아 학생들이 먹는 일이 없도록 하려고 한다. 다만, 이 숫자를 학생들이 바꿔버릴 수 있기 때문에 특정한 규칙으로 초콜릿의 개수를 적으려고 한다.
초콜릿의 종류는 총 5개 있으며 각각 한라봉(H), 감귤(T), 백년초(C), 키위(K), 녹차(G)이다.
남은 초콜릿의 개수를 적는 규칙은 다음과 같다.
첫 번째 줄에 남아있는 초콜릿의 총 개수를 적고, 바로 뒤에7H(개를 아스키 문자로 형상화한 단어)를 적는다.
초콜릿의 총 개수를 적을 때에는 바로 전 단계에 남아있던 초콜릿의 총 개수의 일의 자리의 값을 진법으로 하여 적는다.
단, 바로 전 단계에 남아있던 초콜릿의 총 개수의 일의 자리의 값이 0 또는 1이라면, 10진법으로 적는다.
두 번째 줄에 남아있는 개수가 많은 순으로 각 초콜릿의 종류에 대응하는 알파벳을 공백 없이 적는다.
남아있는 개수가 0개인 초콜릿의 종류에 대응하는 알파벳은 적지 않는다.
남아있는 개수가 동일한 초콜릿의 종류가 여러 개일 경우에는 알파벳 순으로 먼저 오는 것이 앞으로 오도록 적는다.
남아있는 초콜릿의 총 개수가 0개일 경우에는NULL을 적는다.
이제 선생님을 도와서 포스트잇에 적어야 할 초콜릿의 개수를 출력하는 코드를 작성하자!
제한사항
각 종류별 먹는 초콜릿 수의 합은 처음에 있던 종류별 개수보다 작거나 같음이 보장된다.
입출력 예
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
public class JUN27535 {
/* 제주 초콜릿 지키키
* 이번 단계의 총 갯수를 이전 단계의 총 갯수의 일의 자리 진법으로 바꿔야 함
* 이전 단계의 일의 자리가 0, 1이면 그냥 씀
* 끝에 7H 를 붙임
*
* 그 후 많이 남은 순으로 정렬
* 같은 개수면 알파벳 순으로 정렬
* */
// H : 한라봉, T : 감귤, C : 백년초, K : 키위, G : 녹차
static class Choco implements Comparable<Choco> {
char name;
int num;
public Choco(char name, int num) {
this.name = name;
this.num = num;
}
@Override
public int compareTo(Choco o1) {
// 초콜릿 갯수가 같으면 이름 순
if(this.num == o1.num){
//이름은 오름차순
return this.name - o1.name;
}
// 초콜릿 개수별 내림차순
return o1.num - this.num;
}
}
static int N; // 먹는 횟수
static int sum = 0; // 현재 초콜릿 총합
static StringBuilder sb = new StringBuilder(); // 정답 저장
static ArrayList<Choco> list = new ArrayList<>(); // 초콜릿 저장
static ArrayList<Choco> copied = new ArrayList<>(); // 정렬을 위한 리스트
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 초콜릿 입력
list.add(new Choco('H', Integer.parseInt(st.nextToken())));
list.add(new Choco('T', Integer.parseInt(st.nextToken())));
list.add(new Choco('C', Integer.parseInt(st.nextToken())));
list.add(new Choco('K', Integer.parseInt(st.nextToken())));
list.add(new Choco('G', Integer.parseInt(st.nextToken())));
// 현재 초콜릿 총합 구하기, 50일텐데 그냥 구해주자
for(Choco c : list){
sum+=c.num;
}
// 초콜릿 먹을 횟수 입력
N = Integer.parseInt(br.readLine());
int last = sum%10; //일의 자리 구하기
// 초콜릿 먹기 시작
for(int i =0; i < N; i++){
st = new StringTokenizer(br.readLine());
sum = 0;
// 초콜릿 먹으면서 남아있는 초콜릿 갯수 세기
for(int j = 0; j < 5; j++){
list.get(j).num-=Integer.parseInt(st.nextToken());
sum += list.get(j).num;
}
// 이전 총합의 일의 자리 진법으로 바꾸기
sb.append(change(last, sum)).append("7H").append("\n");
// 정렬 하기
if(sum == 0){
// 남아있는 초콜릿이 없으면 NULL 출력해야함
sb.append("NULL").append("\n");
}else{
sortChoco();
for(Choco c : copied){
// 남아 있지 않으면 체크할 필요가 없음
if(c.num == 0) continue;
sb.append(c.name);
}sb.append("\n");
}
// 현재 총합의 일의 자리 저장
last = sum%10;
}
System.out.println(sb);
}
// 이전 총합의 일의 자리로 진법 바꾸기
public static String change(int last, int sum){
StringBuilder num = new StringBuilder();
if(last == 0 || last == 1){
// 전의 총합의 일의 자리가 0, 1이면 10진법으로 하니까 변환 필요 없음
num.append(sum);
return num.toString();
}else{
if(sum == 0){
return "0";
} else{
// 진법 변환 해주기
while(sum != 0){
num.append(sum%last);
sum/=last;
}
}
// 거꾸로 돌려주기 위해 StringBuilder 사용
return num.reverse().toString();
}
}
// 정렬하기: 초콜릿 많은 순으로 정렬
public static void sortChoco(){
// 원본을 정렬하면 뒤에 초콜릿 먹을때 복잡해지니까 복사해서 사용
copied = (ArrayList<Choco>) list.clone();
Collections.sort(copied);
}
}
풀이
진행 순서를 보면
1. 초콜릿 값 넣기
2. 초콜릿을 먹음.
3. 먹고 남은 초콜릿의 총합을
이전 단계의 초콜릿 총합의 일의 자리 진법으로 변환한 후
'7H'를 붙여서 출력
4. 현재 초콜릿의 개수별로 내림차순으로 정렬,
개수가 같을 경우 알파벳 순으로 정렬
1. 초콜릿 저장하기
저는 우선 초콜릿의 이름과 개수를 저장할 클래스를 만들었습니다.
static class Choco implements Comparable<Choco> {
char name;
int num;
public Choco(char name, int num) {
this.name = name;
this.num = num;
}
}
그 후 ArrayList를 만들어서 초코릿을 이름과 개수를 저장했습니다.
2. 초콜릿 먹기
아까 초콜릿을 저장한 list 에서
초콜릿 개수가 저장된 변수에 먹은 만큼 빼주고
합계를 구했습니다.
3. 현재 남아 있는 초콜릿을 전 단계의 총합의 일의 자리 진법으로 변환하기
이건 글 보다는 그림으로 보시면 편하실 것 같아서 열심히 그려왔습니다.
4. 초콜릿 개수로 정렬하기
현재 남아있는 초콜릿 개수가 많은 순으로 정렬을 하면 됩니다.
다만 초콜릿 개수가 같을 때는
알파벳 순으로 정렬을 해주면 됩니다.
평소에 자주 사용하는 정렬은
그냥 비교 대상이 하나였는데
이번에는 비교 조건이 2개가 되어버렸네요 ㅠㅠ
게다가 비교하는게 List.....
어떻게 해야할까요?
이럴때 자주 사용하는게 바로
CompareTo<T>
static class Choco implements Comparable<Choco> {
char name;
int num;
public Choco(char name, int num) {
this.name = name;
this.num = num;
}
// 이 부분입니다!!!!!
@Override
public int compareTo(Choco o1) {
// 초콜릿 갯수가 같으면 이름 순
if(this.num == o1.num){
//이름은 오름차순
return this.name - o1.name;
}
// 초콜릿 개수별 내림차순
return o1.num - this.num;
}
}
static ArrayList<Choco> list = new ArrayList<>();
public static void main(String[] args){
Collections.sort(copied); // 이렇게 사용하시면 됩니다.
}
꼬마 정민이는 이제 A + B 정도는 쉽게 계산할 수 있다. 이제 A + B + C를 계산할 차례이다!
제한사항
첫 번째 줄에 A, B, C (1 ≤ A, B, C ≤ 10^12)이 공백을 사이에 두고 주어진다.
입출력 예
77 77 7777
7931
코드
package com.home;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class JUN11382 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long sum = 0;
for (int i = 0; i < 3; i++) {
sum += Long.parseLong(st.nextToken());
}
System.out.println(sum);
}
}
