가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.
위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매 시간마다 (6,4), (5,3), (4,2), (3,1)로 움직인다.
여러분은 크기 w×h인 격자 공간에서 처음에 (p,q)에서 출발하는 개미의 t시간 후의 위치 (x,y)를 계산하여 출력해야 한다. 개미는 절대 지치지 않고 같은 속력으로 이동한다고 가정한다.
문제에서 w와 h는 자연수이며 범위는 2 ≤ w,h ≤ 40,000이다. 그리고 개미의 초기 위치 p와 q도 자연수이며 범위는 각각 0 < p < w과 0 < q < h이다. 그리고 계산할 시간 t의 범위는 1 ≤ t ≤ 200,000,000이다.
입력
첫줄에는 w와 h가 공백을 사이에 두고 주어진다. 그 다음 줄에는 초기 위치의 좌표값 p와 q가 공백을 사이에 두고 주어진다. 3번째 줄에는 개미가 움직일 시간 t가 주어진다.
출력
출력은 t 시간 후에 개미의 위치 좌표 (x,y)의 값 x와 y를 공백을 사이에 두고 출력한다.
/* 풀이방법 */
대각선으로 움직이는 것은 결국 가로한칸, 세로한칸을 동시에 움직이는 것과 같다!
그리고 높이나 너비로 나누었을때 해당 숫자가 짝수이면 0부터 시작, 홀수이면 벽에서부터 시작한다.
이점을 고려해서 반복문없이 푸는데 성공했으나,
StringBuilder를 사용하지 않아 계속 시간초과가 나서 매우 괴로웠다 ㅠ
(다음 스터디에서는 StringBuilder에 대해 더 공부해봐야겠다.)
/* 해답코드 */
package baekjoon;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
//개미
public class b10158 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int W = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int T = Integer.parseInt(br.readLine());
//짝수면 0에서 출발, 홀수면 벽에서 출발
boolean moveX = (x+T)/W%2==0;
boolean moveY = (y+T)/H%2==0;
x=(x+T)%W;
if(!moveX) {
x=W-x;
}
y=(y+T)%H;
if(!moveY) {
y=H-y;
}
StringBuilder sb = new StringBuilder();
sb.append(x);sb.append(" ");sb.append(y);
bw.write(sb.toString());
bw.flush();
bw.close();
}
}
동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다.
예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. <그림 1>과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다.
< 그림 1 >
1번 상점에서 호출이 들어 왔을 때 동근이가 블록을 시계방향으로 돌아 이동하면 이동 거리가 12가 된다. 반면 반시계방향으로 돌아 이동하면 이동 거리는 18이 된다. 따라서 동근이가 1번 상점으로 가는 최단 거리는 12가 된다. 마찬가지로 동근이의 위치에서 2번 상점까지의 최단 거리는 6, 3번 상점까지의 최단 거리는 5가 된다.
블록의 크기와 상점의 개수 및 위치 그리고 동근이의 위치가 주어질 때 동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄에 하나씩 상점의 위치가 주어진다. 상점의 위치는 두 개의 자연수로 표시된다. 첫째 수는 상점이 위치한 방향을 나타내는데, 1은 블록의 북쪽, 2는 블록의 남쪽, 3은 블록의 서쪽, 4는 블록의 동쪽에 상점이 있음을 의미한다. 둘째 수는 상점이 블록의 북쪽 또는 남쪽에 위치한 경우 블록의 왼쪽 경계로부터의 거리를 나타내고, 상점이 블록의 동쪽 또는 서쪽에 위치한 경우 블록의 위쪽 경계로부터의 거리를 나타낸다. 마지막 줄에는 동근이의 위치가 상점의 위치와 같은 방식으로 주어진다. 상점의 위치나 동근이의 위치는 블록의 꼭짓점이 될 수 없다.
출력
첫째 줄에 동근이의 위치와 각 상점 사이의 최단 거리의 합을 출력한다.
/* 풀이방법 */
처음에 상점이나 동근이 위치를 받을 때, switch문을 사용해 좌표로 바꾸어준다.
이 때, 동근이의 방향(동,서,남,북)만 저장해 놓는다.
그리고 상점 수만큼 반복문을 돌면서,
상점의 좌표가 나올 때까지 turnClockwise메서드를 재귀적으로 실행한다.
만약, 이동한 횟수가 X+Y (동근이가 담당하고 있는 곳은 직사각형 모양의 블록의 가로와 세로를 합한 값)를 넘는다면,
최단 거리가 아니므로, 둘레에서 해당 값을 빼준다.
이동한 횟수를 전부 더해주면 동근이의 위치와 각 상점 사이의 최단 거리의 합 완성이다.
/* 해답코드 */
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//경비원
public class b2564 {
public static int X = 0;
public static int Y = 0;
public static int cnt = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//블록 사이즈와 상점 수 받기
X = Integer.parseInt(st.nextToken());
Y = Integer.parseInt(st.nextToken());
int T = Integer.parseInt(br.readLine());
int dongDir = 0;
//상점,동근이 위치 받기(point[T][]가 동근이)
int[][] point = new int[T+1][2];
for(int i=0;i<T+1;i++) {
st = new StringTokenizer(br.readLine());
int dir = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
switch(dir) {
case 1:
point[i][0]= n;
point[i][1]= Y;
break;
case 2:
point[i][0]= n;
point[i][1]= 0;
break;
case 3:
point[i][0]= 0;
point[i][1]= Y-n;
break;
case 4:
point[i][0]= X;
point[i][1]= Y-n;
break;
}
if(i==T) {
dongDir = dir;
}
}
int sum = 0;
for(int i=0;i<T;i++) {
cnt=0;
turnClockwise(dongDir,point[T][0],point[T][1],point[i][0],point[i][1]);
int r = (cnt<(X+Y)?cnt:2*(X+Y)-cnt);
sum+=r;
//System.out.println(r);
}
System.out.println(sum);
}
public static void turnClockwise(int dir,int x,int y,int tx,int ty) {
if(x==tx&&y==ty) {
return;
}
cnt++;
switch(dir) {
case 3:
if(y+1==Y)dir=1;
turnClockwise(dir,x,y+1,tx,ty);
break;
case 1:
if(x+1==X)dir=4;
turnClockwise(dir,x+1,y,tx,ty);
break;
case 4:
if(y-1==0)dir=2;
turnClockwise(dir,x,y-1,tx,ty);
break;
case 2:
if(x-1==0)dir=3;
turnClockwise(dir,x-1,y,tx,ty);
break;
}
}
}
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.
예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.
입력
첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다
출력
첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.
/* 풀이법 */
단순하게 생각해서 100*100 도화지를 만들었다.
입력 받은 색종이 좌표를 이용하여, 색종이 영역은 모두 true로 바꿔준다.
추후 true의 개수만 세면 된다!
/* 해답코드 */
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//색종이
public class b2563 {
public static boolean[][] paper = new boolean[100][100];
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
for(int i=0;i<T;i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
for(int dx=0;dx<10;dx++) {
for(int dy=0;dy<10;dy++) {
paper[y+dy][x+dx]=true;
}
}
}
int size =0 ;
for(int x=0;x<100;x++){
for(int y=0;y<100;y++){
if(paper[y][x])
size++;
}
}
System.out.println(size);
}
}
0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라.
예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4, 1, 3, 3, 2, 2, 9, 2, 3 의 경우에는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1, 5, 3, 6, 4, 7, 1, 3, 2, 9, 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.
입력
첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.
출력
첫째 줄에 가장 긴 길이를 출력한다.
/* 풀이법 */
이전 숫자를 beforeNum에 저장한다.
입력을 받은 숫자가 이전 숫자보다 크다면 asc배열에 해당 인덱스의 값을 (이전 인덱스 값+1)로 저장한다.
그리고 desc배열에 해당 인덱스 값을 1로 바꾼다.
입력을 받은 숫자가 이전 숫자보다 작다면 desc배열에 해당 인덱스의 값을 (이전 인덱스 값+1)로 저장한다.
그리고 asc배열에 해당 인덱스 값을 1로 바꾼다.
만약 이전 숫자와 값이 같다면 asc배열과 desc배열 둘 다 (이전 인덱스 값 +1)을 해준다.
/* 해답코드 */
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class b2491 {
public static void main(String[] args) throws IOException {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] asc = new int[N];
int[] desc = new int[N];
int beforeNum = Integer.parseInt(st.nextToken());
asc[0]=1; desc[0]=1;
for(int i=1;i<N;i++) {
int num = Integer.parseInt(st.nextToken());
if(num < beforeNum) {
desc[i] = desc[i-1]+1;
asc[i] = 1;
}else if(num > beforeNum) {
asc[i] = asc[i-1]+1;
desc[i] = 1;
}else if(num == beforeNum) {
asc[i] = asc[i-1]+1;
desc[i] = desc[i-1]+1;
}
beforeNum = num;
}
int max=0;
for(int i=0;i<N;i++) {
if(max<asc[i])
max=asc[i];
if(max<desc[i])
max=desc[i];
}
System.out.println(max);
}
}
평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다.
매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다.
중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다.
떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다.
JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자.
입력
교수님이 출력을 원하는 재귀 횟수 N(1 ≤ N ≤ 50)이 주어진다.
출력
출력 예시를 보고 재귀 횟수에 따른 챗봇의 응답을 출력한다.
/* 재귀 함수 */
"어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다." >> 처음에 한번만 출력
<재귀의 시작>
"재귀함수가 뭔가요?"
if
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
else
"재귀함수는 자기 자신을 호출하는 함수라네"
<재귀의 마무리>
라고 답변하였지.
어떤 부분이 어느 부분에 나와야 하는지 침착하게 보면 풀 수 있다.
/* 해답코드 */
package baekjoon;
import java.util.Scanner;
public class b17478 {
static int cnt=0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
cnt = sc.nextInt();
System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
askHim(0,"");
sc.close();
}
static void askHim(int n,String line) {
if(cnt>n) {
System.out.println(line + "\"재귀함수가 뭔가요?\"");
System.out.println(line + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
System.out.println(line + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
System.out.println(line + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
askHim(n+1,line+"____");
}else {
System.out.println(line + "\"재귀함수가 뭔가요?\"");
System.out.println(line + "\"재귀함수는 자기 자신을 호출하는 함수라네\"");
}
System.out.println(line + "라고 답변하였지.");
return;
}
}
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.
/* 재귀 함수 */
" flat하게 생각하자 "
하나의 디스크 입장에서
- (전체 디스크 개수 - 1)만큼 들어서 시작 막대기에서 임시 막대기로 놓고,
- 해당 디스크를 목적지로 옮기고,
- (전체 디스크 개수 - 1)만큼 들어서 임시 막대기에서 목적지로 옮긴다.
/* 해답코드 */
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//하노이 탑
public class b11729 {
static int cnt = 0;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int disk = Integer.parseInt(bf.readLine());
move(disk,1,2,3);
System.out.println(cnt);
System.out.println(sb);
}
public static void move(int disk,int start, int temp, int dstn) {
if(disk==0) return;
cnt++;
move(disk-1,start,dstn,temp);
sb.append(start+" "+dstn+"\n");
move(disk-1,temp,start,dstn);
}
}
