3월 1주차 스터디 문제 목록
백준 1063번 킹
백준 1620 나는야포켓몬마스터이다솜
백준 18429 근손실
백준 14499 주사위 굴리기
2021년 3월 4일
이번 문제는 대체로 평이했다, 전에는 건들지도 못했을만한 문제들이 서서히 어떻게 풀어야하는지 보이기 시작하고 또 풀리니까 너무 재미있다. 정말 오랜만이다 공부가 재밌어진건 뭔가 수학문제를 푸는거 같아서 재미있고 공부처럼 느껴지지 않는다는게 정말 알고리즘의 묘미인것같다. 한가지 걱정인게 문제 풀이가 너무 정형화 되고 있어서 조금 다른 방식의 문제를 풀어야 할 경우 정형화된 방법만 생각이나서 접근을 못하는 문제가 생기는것이다! 조금 더 다양한 문제를 접하면서 또 지금 풀이법은 체득이 될 정도로 익숙해지자!
백준 1063 킹
구현 전 생각
이동 메소드를 하나 만들어서
1.먼저 방향을 판단한다. (팔방탐색)
2.NX,NY 변수를 이용해서 앞으로 진행할 방향의 진행가능성을 확인한다.
3.만약에 진행하고자 하는곳에 돌이 존재하는경우
4.그 돌을 먼저 이동 시킨 후 킹의 위치도 이동 시켜준다 (이때 돌의 다음 위치를 확인)
아쉬운점
1.먼저 돌이 이동하지 못한 경우를 체크하지 못하였습니다.
- 반례들을 보고 해결함 문제를 너무 얕게만 보지말고 깊게 생각하는 습관을 만들자.
2.dx,dy를 헷갈려서 반대로 적은것 문제를 확실히 확인 할것!
- 전에도 같은 문제로 틀린 적 있음!!
- 시뮬레이션에 맞게 최대한 꼼꼼히 생각 할 것!
코드(pass)
package com.study25;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class backjoon_1063_킹 {
static int[][] map = new int[8][8];
static int x,y,sx,sy;
//R,L,B,T,RT,LT,RB,LB
static int[] dy= {0,0,-1,1,1,1,-1,-1};
static int[] dx= {1,-1,0,0,1,-1,1,-1};
public static void go (String A,int x1,int y1,int state) {
int dir=0;
switch(A) {
case "R":
dir = 0;
break;
case "L":
dir = 1;
break;
case "B":
dir= 2;
break;
case "T":
dir = 3;
break;
case "RT":
dir = 4;
break;
case "LT":
dir = 5;
break;
case "RB":
dir = 6;
break;
case "LB":
dir = 7;
break;
}
int nx = x1+dx[dir];
int ny = y1+dy[dir];
//범위를 벗어나는경우
if(nx<0||ny<0||nx>=8||ny>=8) return;
//돌이 이동하려고 하는곳에 있는경우
if(map[nx][ny]==2) {
//STATE 2로 변경해주고 GO 메소드 사용
go(A,nx,ny,2);
//돌이 밖으로 나가지 않은 경우를 확인하기 위한 조건문
//돌이 밖으로 나가면 킹도 같이 나가면 안된다.
if(map[nx][ny]==0) {
map[x][y]=0;
x=nx;
y=ny;
map[x][y]=1;
}
return;
}
//돌이 이동하는 경우
if(state==2) {
map[sx][sy]=0;
sx=nx;
sy=ny;
map[sx][sy]=2;
return;
}
//킹이 이동하는 경우
map[x][y]=0;
x=nx;
y=ny;
map[x][y]=1;
return;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//킹의 위치
String king = st.nextToken();
x =king.charAt(0)-'A';
y =king.charAt(1)-'1';
map[x][y]=1;
//돌의 위치
String stone = st.nextToken();
sx = stone.charAt(0)-'A';
sy = stone.charAt(1)-'1';
map[sx][sy]=2;
int move = Integer.parseInt(st.nextToken());
for (int i = 0; i < move; i++) {
st = new StringTokenizer(br.readLine()," ");
String A = st.nextToken();
go(A,x,y,1);
}
char result = (char) (x+'A');
char result2= (char) (sx+'A');
//1로 빼주었기 때문에 +1 해야한다.
System.out.println(result+""+(y+1));
System.out.println(result2+""+(sy+1));
}
}
백준 1620 나는야 포켓몬 마스터 이다솜
구현전 생각
1.첫번째 아이디어
먼저 입력을 받아 배열에 저장하고
String에 '0'~'100000' 을 빼서 숫자이면 배열에서 그 데이터값을 가지고오고 이름이면 그 배열에서 숫자를 가지고온다.
2.두번째 아이디어
먼저 입력받은 도감을 해쉬맵에 저장하고 그 해쉬맵에서 키값과 밸류값으로 검색한 후에 해당하는 밸류 값과 키값을 출력하는 방법
아쉬운점
1. 첫번째 아이디어에서 생각하지 못한 점은 출력 시간을 생각 하지 않았다 O(N^2) 시간이 걸림으로 통과 못하는 방법
-> IM 시험을 볼때도 그렇고 항상 먼저 시간을 확인하고 가능한지 먼저 확인하자.
2. 해쉬맵에 대한 공부가 완벽히 되어 있지 않아서 다시 검색하고 풀어야 했다. 너무 얕게 알고 있었던것 같다 해쉬맵의 경우 키값으로 밸류값을 찾을순 있지만 밸류값으로 키값을 찾기 위해서 탐색 작업을 해주어야한다. 이 문제를 해결 하기 위해서 두개의 해쉬맵을 사용했다.
코드 (잘못 푼 방식)
탐색 방법에
package com.study26;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class backjoon_1620_나는야포켓몬마스터이다솜 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String[] dogam= new String[N+1];
for (int i = 1; i <=N; i++) {
st = new StringTokenizer(br.readLine());
dogam[i]= st.nextToken();
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String temp = st.nextToken();
//숫자면
if(temp.charAt(0)>='1'&&temp.charAt(0)<='9')
{
int S = Integer.parseInt(temp);
System.out.println(dogam[S]);
}
else {
for (int j = 0; j < dogam.length; j++) {
if(temp.equals(dogam[j])) {
System.out.println(j);
}
}
}
}
}
} 코드 (Pass)
package com.study26;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;
public class backjoon_1620_나는야포켓몬마스터이다솜 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String[] dogam= new String[N+1];
HashMap<Integer,String> map = new HashMap<>();
HashMap<String,Integer> map2 = new HashMap<>();
for (int i = 1; i <=N; i++) {
st = new StringTokenizer(br.readLine());
String temp = st.nextToken();
map.put(i, temp);
map2.put(temp,i);
}
for (int i = 0; i <M; i++) {
st = new StringTokenizer(br.readLine());
String temp = st.nextToken();
//숫자면
if(temp.charAt(0)>='1'&&temp.charAt(0)<='9')
{
int S = Integer.parseInt(temp);
//System.out.println(dogam[S]);
wr.write(map.get(S)+"\n");
wr.flush();
}
else {
//System.out.println(j);
wr.write(map2.get(temp)+"\n");
wr.flush();
}
}
wr.close();
}
}
백준 18429 근손실
구현 전 생각
이 문제는 키트 번호를 순열을 이용하여 키트를 완전 탐색하는 방법으로 해결할것이다.
거기에 중량이 500밑으로 내려가는 경우를 리턴하여 백프로파게이션으로 구현 하면 될것같다.
최대 일수가 N이고 키트 갯수가 50이라 시간 제한안에 해결 가능할것 같다.
아쉬운점
순열을 만들때 바로 계산해주면 필요 없는 순열을 만들지 않아서 더 빠르게 동작 할것 같다!
->구현 결과 : 더 빠르지는 않았지만 훨씬더 간단한 코드가 완성 되었다. 아마도 더 빠르게 작성하려고 하면 재귀를 사용하지 않고 직접적으로 포문을 사용할것
코드(간단한 버전)
package com.study26;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class backjoon_18429_근손실 {
static int N,K;
static int[] kit;
static int[] numbers;
static boolean isSelected[];
static int cntNum=0;;
public static void permutation(int cnt,int weight) {
//순열이 키트의 개수 만큼 다 만들어진 경우
if(weight<0) return;
if(cnt == N) {
cntNum++;
return;
}
for (int i = 0; i < N; i++) {
if(isSelected[i]) continue;
isSelected[i] = true;
permutation(cnt+1,weight+kit[i]-K);
isSelected[i] = false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
kit = new int[N];
numbers= new int[N];
isSelected= new boolean[N];
st = new StringTokenizer(br.readLine()," ");
for (int i = 0; i < N; i++) {
kit[i]= Integer.parseInt(st.nextToken());
}
//순열 사용
permutation(0,0);
System.out.println(cntNum);
}
}
코드(pass)
package com.study26;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class backjoon_18429_근손실 {
static int N,K;
static int[] kit;
static int[] numbers;
static boolean isSelected[];
static int cntNum;
public static void permutation(int cnt) {
//순열이 키트의 개수 만큼 다 만들어진 경우
if(cnt == N) {
sum();
return;
}
for (int i = 0; i < N; i++) {
if(isSelected[i]) continue;
numbers[cnt]=i;
isSelected[i] = true;
permutation(cnt+1);
isSelected[i] = false;
}
}
public static void sum() {
int temp=0;
for (int i = 0; i < N; i++) {
//중량에 키트를 먼저 더한후 오늘 빠져나가는 중량을 빼준다
temp=temp+kit[numbers[i]];
temp-=K;
//만약 음수가 나오면 500밑으로 떨어진 경우기 때문에 리턴
if(temp<0) return;
}
//키트가 음수가 되지 않으면 가능한 것임으로 카운트를 +1
cntNum++;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
kit = new int[N];
numbers= new int[N];
isSelected= new boolean[N];
st = new StringTokenizer(br.readLine()," ");
for (int i = 0; i < N; i++) {
kit[i]= Integer.parseInt(st.nextToken());
}
//순열 사용
permutation(0);
System.out.println(cntNum);
}
}
백준 14499 주사위 굴리기
구현 전 생각
주사위 배열을 만들어서 주사위가 굴러가는 것을 배열로 코딩
2
4 1 3
5
6
이런 식으로 구성 되어 있으니 오른쪽으로 한칸 가게 되면
밑면이 3으로 가고 4가 윗면이 된다. 이걸 조금더 간단하게 생각하면 지금 보면 마주보는 인덱스의 합이 7인것을 알 수 있다 따라서 index가 밑면으로 갈때 7-index의 값을 해서 맞은편의 값을 출력하는 방식으로 해결
->나머지는 이제 입력이 들어올때 탐색하는 방법으로 nx,ny를 사용하여 벗어나는 경우 리턴을 해서 출력을 하지 않고 이동도 하지 않는다.
아쉬운점
1.틀린 아이디어
이 문제는 내가 생각했던 방식으로 구현 되지 않았다. 나는 밑면을 고정하고 시작해서 내가 모든 주사위의 방향을 예측할 수 있을것이라 생각하고 indexmove에 주사위의 예상 진행 방향 미리 나열 하였으나 주사위가 회전함으로 위 아래가 바뀔 수 있다는 생각을 하지 못한 점 이 생각에서 벗어나지 못해서 많은 시간을 소비 했다.
그래서 주사위의 진행 방향을 단순하게 생각했다. 수정한 코드에서는 배열의 인덱스를 직접적으로 넣어줘서 주사위의 변화를 반영했다.
예를 들면, 밑변이 6일때 동쪽으로 이동하게 되면 밑면이였던 2156은 3의 옆면이 되고 4가 윗면이 된다.
코드
package com.study26;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class backjoon_14499_주사위굴리기 {
static int N,M,x,y,index;
static int[] dice = new int[7];
static int[][] map;
//동 서 북 남
static int[] dx= {0,0,0,-1,1};
static int[] dy= {0,1,-1,0,0};
//static int[][] indexmove = {{0,0,0,0,0,0},{1,3,4,2,5,6},{2,3,4,6,1,5},{3,6,1,2,5,4},{4,1,6,2,5,3},{5,3,4,1,6,2},{6,3,4,5,2,1}};
public static void move(int dir) {
int nx = x+dx[dir];
int ny = y+dy[dir];
if(nx<0||ny<0||nx>=N||ny>=M) return;
//이동이 가능 하면 주사위 변경
changedice(dir);
// System.out.println("index :" + index);
// System.out.println("dir: "+dir);
// System.out.println("nindex : "+nindex);
// System.out.println("저장될 값 : "+map[nx][ny]);
if (map[nx][ny] == 0)
map[nx][ny] = dice[6];
else{
dice[6] = map[nx][ny];
map[nx][ny] = 0;
}
System.out.println(dice[1]);
x = nx;
y = ny;
}
public static void changedice(int dir) {
int temp = dice[1];
switch(dir) {
case 1:
//dice ={0,dice[4],dice[2],dice[1],dice[6],dice[5],dice[3]};
dice[1] =dice[4];
dice[4] = dice[6];
dice[6] = dice[3];
dice[3] = temp;
break;
case 2:
//dice = {0, dice[3], dice[2], dice[6], dice[1], dice[5], dice[4]};
dice[1]=dice[3];
dice[3]=dice[6];
dice[6]=dice[4];
dice[4]=temp;
break;
case 3:
//dice = {0, dice[5], dice[1], dice[3], dice[4], dice[6], dice[2]};
dice[1]=dice[5];
dice[5]=dice[6];
dice[6]=dice[2];
dice[2]=temp;
break;
case 4:
//dice = {0, dice[2], dice[6], dice[3], dice[4], dice[1], dice[5]};
dice[1]=dice[2];
dice[2]=dice[6];
dice[6]=dice[5];
dice[5]=temp;
break;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
dice = new int[7];
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
map = new int[N][M];
int move = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine()," ");
for (int j = 0; j < M; j++) {
map[i][j]=Integer.parseInt(st.nextToken());
}
}
index=6;
st = new StringTokenizer(br.readLine()," ");
for (int i = 0; i < move ; i++) {
int tmp = Integer.parseInt(st.nextToken());
move(tmp);
}
}
}
코린이