swea 1486 장훈이의 높은 선반
점원 1명의 합에서 n명의 합까지 B와 비교하여 최소값을 구한다.
틀린이유 : 시간 초과를 생각해서 1명 부터 오름 차순으로 n명의 키합을 구했을 때 b보다 큰 값이 갱신이 되면 끝이라고 생각했는데 n명의 합보다 n+1명의 합이 더 작을 경우가 존재하므로 모든 경우의 수를 따져야함
package algo;
import java.util.Scanner;
public class swea1486 {
static Scanner scan = new Scanner(System.in);
static int N,B;
static int[] arr;
static int min;
public static void main(String[] args) {
// TODO Auto-generated method stub
int t=scan.nextInt();
for(int o=1;o<=t;o++) {
min=Integer.MAX_VALUE;
N=scan.nextInt(); //점원의 수
B=scan.nextInt(); //선반의 높이
arr=new int[N];
for(int i=0;i<N;i++) { //점원들의 키
arr[i]=scan.nextInt();
if(arr[i]>=B) {
min=Math.min(arr[i], min);
}
}
for(int i=2;i<=N;i++) {
sol(i,0,0,0);
}
System.out.println("#"+o+" "+(min-B));
}
}
public static void sol(int end,int depth,int start,int sum) {
if(depth==end) {
if(sum>=B) {
min=Math.min(sum, min);
}
return;
}
for(int i=start;i<N;i++) {
sum+=arr[i];
sol(end,depth+1,i+1,sum);
sum-=arr[i];
}
}
}
swea 2112 보호필름
생각한 로직
약품 n개 주입 했을 때(a일때b일때)의 경우의 수 완탐
0개부터 주입하여 조건을 만족했을때 끝내기
틀린 부분
변경한 배열 원상복구 안해줌
뽑은거 다시 뽑을 수 있게 중복조합으로 만들어서 무한루프
-> start index 부터 for문을 돌거나 visited 체크를 해야함
정답코드
import java.util.Scanner;
public class swea2112 {
static int D,W,K,ANS;
static int [][] arr;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
for (int o = 1; o <= t; o++) {
D=scan.nextInt();
W=scan.nextInt();
K=scan.nextInt();
ANS=0;
arr=new int[D][W];
for(int i=0;i<D;i++) {
for(int j=0;j<W;j++) {
arr[i][j]=scan.nextInt();
}
}
//0회 주입 할 때
if(check(arr)) {
ANS=0;
}
else {
sol();
}
System.out.println("#"+o+" "+ANS);
}
}
public static void sol() {
//원본 배열 보존
int[][] new_arr=new int[D][W];
int i=1; //약 주입하는 횟수
while(true) {
arr_copy(arr,new_arr);
choice(new_arr,i,0,0);
if(ANS!=0) {
break;
}
i++;
// System.out.println("loop sol------------");
}
return;
}
public static void choice(int [][] new_arr,int in_num,int depth,int start) { //조합으로 주입할곳 선택
if(depth==in_num) {
//체크
// print(new_arr);
if(check(new_arr)) {// 체크가 true이면
ANS=in_num;
return;
}
return;
}
for(int i=start;i<D;i++) { //주입할 위치 선택
for(int j=0;j<=1;j++) { //a or b 선택
injection(new_arr,i,j); //주입
//다음 선택
choice(new_arr,in_num,depth+1,i+1);
//원상 복구
}
recover(new_arr,i);
}
}
public static void injection(int[][] new_arr,int d,int type) {
// System.out.println("injection"+ d+" type "+ type);
for(int j=0;j<W;j++) {
new_arr[d][j]=type;
}
}
public static void recover(int[][] new_arr,int d){
// System.out.println("recover"+ d);
for(int i=0;i<W;i++) {
new_arr[d][i]=arr[d][i];
}
}
public static void arr_copy(int[][] arr,int[][]new_arr) {
for(int i=0;i<D;i++) {
for(int j=0;j<W;j++) {
new_arr[i][j]=arr[i][j];
}
}
}
public static boolean check(int[][] new_arr) {
for(int i=0;i<W;i++) {
int last=new_arr[0][i];
int cnt=0;
int max=0;
for(int j=0;j<D;j++) {
if(last==new_arr[j][i]) {
cnt++;
if(cnt>max) {
max=cnt;
}
}
else {
last=new_arr[j][i];
cnt=1;
}
}
if(max>=K) {//두께보다 두꺼움
continue;
}
else return false;
}
return true;
}
public static void print(int [][] new_arr) {
for(int i=0;i<D;i++) {
for(int j=0;j<W;j++) {
System.out.print(new_arr[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
}
//약품 n개 주입 했을 때(a일때b일때) 완탐
//swea 4193 수영대회
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class swea4193 {
static class point{
int x,y;
point(int x,int y) {
this.x=x;
this.y=y;
}
}
static Scanner scan = new Scanner(System.in);
static int N,A,B,C,D;
static int [][] arr;
static int[] dx = { 0, 1, 0, -1 };
static int[] dy = { 1, 0, -1, 0 };
static int min;
public static void main(String[] args) {
// TODO Auto-generated method stub
int T=scan.nextInt();
for(int o=0;o<T;o++) {
min=Integer.MAX_VALUE;
N=scan.nextInt();
arr=new int[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
arr[i][j]=scan.nextInt();
}
}
A=scan.nextInt();
B=scan.nextInt();
C=scan.nextInt();
D=scan.nextInt();
sol();
if(min==Integer.MAX_VALUE) {
System.out.println("#"+(o+1)+" "+-1);
}
else System.out.println("#"+(o+1)+" "+(min+1));
}
}
public static void sol() {
Queue<point> q=new LinkedList<>();
boolean[][] visited=new boolean [N][N];
q.offer(new point(A,B));
visited[A][B]=true;
int sec=0;
boolean flag=false;
while(!q.isEmpty()) {
int size=q.size();
if((sec-2)%3==0) {//소용돌이가 없어지는 초
flag=true;
}else flag=false;
if(sec>=min) break;
for(int i=0;i<size;i++) {
point cur=q.poll();
for(int a=0;a<4;a++) {
int nx=cur.x+dx[a];
int ny=cur.y+dy[a];
if(nx>=0&&ny>=0&&nx<N&&ny<N) {
if(arr[nx][ny]!=1&&!visited[nx][ny]) {
if(arr[nx][ny]==2&&!flag) {
q.offer(new point(cur.x,cur.y));//대기
}
else {
q.offer(new point(nx,ny));
visited[nx][ny]=true;
if(nx==C&&ny==D) {
min=Math.min(sec, min);
}
}
}
}
}
}
sec++;
}
}
}소용돌이 일때는 방문처리 안하고 cur을 q에 넣어서 대기 처리
소용돌이가 사라지는 때는 나머지가 2일때
도착하지 못할때는 -1처리
swea 2382 미생물 격리
swea4008 숫자 만들기
생각한 로직 : dfs 중복조합을 visited체크하며 해준
import java.util.Scanner;
public class swea4008 {
static int N,max,min;
static int[] arr,arr2;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
for (int o = 1; o <= t; o++) {
max=Integer.MIN_VALUE;
min=Integer.MAX_VALUE;
N=scan.nextInt();
arr=new int[4];
arr2=new int[N];
for(int i=0;i<4;i++) {
arr[i]=scan.nextInt();
}
for(int j=0;j<N;j++) {
arr2[j]=scan.nextInt();
}
dfs(1,arr2[0]);
System.out.println("#"+o+" "+(max-min));
}
}
public static int cal(int a,int b,int c) {
int ans=0;
if(b==0) {
ans= a+c;
}
else if(b==1) {
ans= a-c;
}
else if(b==2) {
ans= a*c;
}
else if(b==3) {
ans=a/c;
}
return ans;
}
public static void dfs(int depth,int result) {
if(depth==N) {
if(max<result) {
max=result;
}
if(min>result) {
min=result;
}
return;
}
for(int i=0;i<4;i++) {
if(arr[i]>0) {
arr[i]--;
int r=cal(result,i,arr2[depth]);
dfs(depth+1,r);
arr[i]++;
}
}
}
}SWEA 1949 등산로 조성
첫번째 시도한 풀이 방법 :
n*n돌면서 각칸 k만큼 깎기 ->가장 높은 봉우리 찾기 -> 낮은곳으로 dfs
틀린 이유 :
1. 문제를 잘못읽음 -> 처음 입력에서 가장 높은 봉우리가 시작점이여야한다(문제가 설명이 좀 부족했던듯)
2. 문제를 잘못읽음 -> 최대 k만큼 깍는거라서 1부터 k만큼깎는 경우를 다 고려해야한다.
(49/51) 틀린코드
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class pos2 {
int x;
int y;
int dep;
pos2(int x, int y, int dep) {
this.x = x;
this.y = y;
this.dep = dep;
}
}
public class swea194 {
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
static int n, k;
static int[][] arr;
static int MAX;
static Queue<pos2> q;
static boolean[][] visited;
static int max = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
for (int o = 1; o <= t; o++) {
max = 0;
int cnt=0;
n = scan.nextInt();
k = scan.nextInt();
arr = new int[n][n];
MAX = 0;
ArrayList<pos2> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = scan.nextInt();
if (arr[i][j] >= MAX) {
MAX = arr[i][j];
cnt++;
}
}
}
// 깎기
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] -= k;
for (int a = 0; a < n; a++) {
for (int b = 0; b < n; b++) {
if (arr[a][b] == MAX) { //시작점
visited=new boolean[n][n];
visited[a][b]=true;
dfs(a,b,0);
}
}
}
arr[i][j]+=k;//원상복구
}
}
System.out.println("#"+o+" "+(max+1));
}
}
public static void dfs(int i,int j,int depth) {
for(int a=0;a<4;a++) {
int nx=i+dx[a];
int ny=j+dy[a];
if(nx>=0&&ny>=0&&nx<n&&ny<n&&!visited[nx][ny]) {
if(arr[nx][ny]<arr[i][j]) {
if(max<depth+1) {
max=depth+1;
}
// System.out.println(arr[nx][ny]+" "+(depth));
visited[nx][ny]=true;
dfs(nx,ny,depth+1);
visited[nx][ny]=false;
}
}
}
}
}
정답 코드
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class pos2 {
int x;
int y;
int dep;
pos2(int x, int y, int dep) {
this.x = x;
this.y = y;
this.dep = dep;
}
}
public class swea194 {
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
static int n, k;
static int[][] arr;
static int MAX;
static Queue<pos2> q;
static boolean[][] visited;
static int max = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
for (int o = 1; o <= t; o++) {
max = 0;
int cnt=0;
n = scan.nextInt();
k = scan.nextInt();
arr = new int[n][n];
MAX = 0;
ArrayList<pos2> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = scan.nextInt();
if (arr[i][j] >= MAX) {
MAX = arr[i][j];
cnt++;
}
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(arr[i][j]==MAX) {
list.add(new pos2(i,j,0));
}
}
}
// 깎기
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for(int m=1;m<=k;m++) {
arr[i][j] -= m;
for(int a=0;a<list.size();a++) {
pos2 pos =list.get(a);
if(pos.x==i&&pos.y==j)continue;
visited=new boolean[n][n];
visited[pos.x][pos.y]=true;
dfs(pos.x,pos.y,0);
}
arr[i][j]+=m;//원상복구
}
}
}
System.out.println("#"+o+" "+(max+1));
}
}
public static void dfs(int i,int j,int depth) {
for(int a=0;a<4;a++) {
int nx=i+dx[a];
int ny=j+dy[a];
if(nx>=0&&ny>=0&&nx<n&&ny<n&&!visited[nx][ny]) {
if(arr[nx][ny]<arr[i][j]) {
if(max<depth+1) {
max=depth+1;
}
visited[nx][ny]=true;
dfs(nx,ny,depth+1);
visited[nx][ny]=false;
}
}
}
}
}swea 1953 탈주범 검거
생각한 로직 : 상하좌우 움직일 수있는지 없느지를 담는 클래스 만든다 -> 현재위치에서 블럭에 해당하는 상하좌우 true false를 찾는다.(다음칸이 빈칸이여도 안됨 격자밖이여도안됨 )-> 해당하는 방향을 bfs한다. 해당하는 depth가 될때까지 반복한다. (visited 체크한다.)
틀린 이유 : 다음 배관의 방향도 체크해야함, depth가 L보다 작을때만 큐에 넣어줘야함
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class pos {
int x;
int y;
int dep;
pos(int x, int y, int dep) {
this.x = x;
this.y = y;
this.dep = dep;
}
}
public class swea1953 {
static int N,M,R,C,L;
static int[][] arr;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
for (int o = 1; o <= t; o++) {
N=scan.nextInt();
M=scan.nextInt();
//맨홀 (시작점)
R=scan.nextInt();
C=scan.nextInt();
//소요시간 (depth)
L=scan.nextInt();
arr=new int[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
arr[i][j]=scan.nextInt(); //배관 정보
}
}
int ans=bfs(R,C);
System.out.println("#"+o+" "+ans);
}
}
public static int bfs(int R, int C) {
int cnt=1;
boolean visited[][]=new boolean[N][M];
Queue<pos> q=new LinkedList<>();
q.offer(new pos(R,C,1));
visited[R][C]=true;
while(!q.isEmpty()) {
pos cur=q.poll();
boolean[] dir=move(arr[cur.x][cur.y]);
for(int i=0;i<4;i++) {
if(!dir[i]) continue;
int nx=cur.x+dx[i];
int ny=cur.y+dy[i];
if(nx>=0&&ny>=0&&nx<N&&ny<M&&!visited[nx][ny]&&cur.dep<L&&arr[nx][ny]>0) {
boolean[] dir2=move(arr[nx][ny]);
boolean flag=false;
if(i==0&&dir2[1]) {
flag=true;
}
else if(i==1&&dir2[0]) {
flag=true;
}
else if(i==2&&dir2[3]) {
flag=true;
}
else if(i==3&&dir2[2]) {
flag=true;
}
if(flag) {
visited[nx][ny]=true;
q.offer(new pos(nx,ny,cur.dep+1));
cnt++;
}
}
}
}
return cnt;
}
public static boolean[] move(int type) {
boolean[] arr = null;
if(type==1) {
arr= new boolean[] {true,true,true,true};
}
else if(type==2) {
arr= new boolean[] {true,true,false,false};
}
else if(type==3) {
arr= new boolean[] {false,false,true,true};
}
else if(type==4) {
arr= new boolean[] {true,false,false,true};
}
else if(type==5) {
arr= new boolean[] {false,true,false,true};
}
else if(type==6) {
arr= new boolean[] {false,true,true,false};
}
else if(type==7) {
arr= new boolean[] {true,false,true,false};
}
return arr;
}
}swea 8382 방향전환
public class swea8382 {
static Scanner scan = new Scanner(System.in);
public static void main(String[] args) {
// TODO Auto-generated method stub
int T=scan.nextInt();
for(int o=0;o<T;o++) {
int x1=scan.nextInt();
int y1=scan.nextInt();
int x2=scan.nextInt();
int y2=scan.nextInt();
int x=Math.abs(x2-x1);
int y=Math.abs(y2-y1);
int s=Math.min(x,y);
int rest=Math.abs((x-s)-(y-s));
if(rest%2==0) {
System.out.println("#"+(o+1)+" "+((rest*2)+2*s));
}else System.out.println("#"+(o+1)+" "+((rest*2-1)+2*s));
}
}
}두 좌표의 차 구하기
=> 원점에서 거기까지 가는것과 같음
n,n까지 가는건 n*2
나머지 가야할 길은 두좌표의 차 두개를 뺀 값 (abs)
홀수일때는 2n-1
짝수일때는 2n 만큼이 걸린다.
남기고 싶은 개발자입니다 :>