'알고리즘 공부' 카테고리의 글 목록

알고리즘 공부

백준 - 구간 합 구하기2

컴퓨터과학 2024. 7. 17. 00:04

2024. 7. 17. 00:04

https://www.acmicpc.net/problem/10999

문제가 좀 많이 어렵네요.

세그먼트 트리 + lazy propagation 알고리즘인데... 습 좀 많이 어렵네요.

관련해서 오답노트 정리 해볼 예정입니다.

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static long[] tree;
    static long[] lazy;

    public static void initTree(long[] arr) {
        buildTree(0, n - 1, 1, arr);
    }

    public static long buildTree(int start, int end, int node, long[] arr) {
        if (start == end) {
            return tree[node] = arr[start];
        }

        int mid = (start + end) / 2;
        return tree[node] = buildTree(start, mid, node * 2, arr) + buildTree(mid + 1, end, node * 2 + 1, arr);
    }

    public static void updateRange(int start, int end, int node, int rangeStart, int rangeEnd, long diff) {
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1) * lazy[node];
            if (start != end) {
                lazy[node * 2] += lazy[node];
                lazy[node * 2 + 1] += lazy[node];
            }
            lazy[node] = 0;
        }

        if (rangeStart > end || rangeEnd < start) {
            return;
        }

        if (rangeStart <= start && end <= rangeEnd) {
            tree[node] += (end - start + 1) * diff;
            if (start != end) {
                lazy[node * 2] += diff;
                lazy[node * 2 + 1] += diff;
            }
            return;
        }

        int mid = (start + end) / 2;
        updateRange(start, mid, node * 2, rangeStart, rangeEnd, diff);
        updateRange(mid + 1, end, node * 2 + 1, rangeStart, rangeEnd, diff);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    public static long queryRange(int start, int end, int node, int queryStart, int queryEnd) {
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1) * lazy[node];
            if (start != end) {
                lazy[node * 2] += lazy[node];
                lazy[node * 2 + 1] += lazy[node];
            }
            lazy[node] = 0;
        }

        if (queryStart > end || queryEnd < start) {
            return 0;
        }

        if (queryStart <= start && end <= queryEnd) {
            return tree[node];
        }

        int mid = (start + end) / 2;
        return queryRange(start, mid, node * 2, queryStart, queryEnd) + queryRange(mid + 1, end, node * 2 + 1, queryStart, queryEnd);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }

        tree = new long[n * 4];
        lazy = new long[n * 4];

        initTree(arr);

        for (int i = 0; i < m + k; i++) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            if (type == 1) {
                int b = Integer.parseInt(st.nextToken()) - 1;
                int c = Integer.parseInt(st.nextToken()) - 1;
                long d = Long.parseLong(st.nextToken());
                updateRange(0, n - 1, 1, b, c, d);
            } else if (type == 2) {
                int b = Integer.parseInt(st.nextToken()) - 1;
                int c = Integer.parseInt(st.nextToken()) - 1;
                long result = queryRange(0, n - 1, 1, b, c);
                System.out.println(result);
            }
        }

    }
}

'알고리즘 공부' 카테고리의 다른 글

백준 수열과 쿼리 37 (2)	2024.07.15
백준 커피숍2 (0)	2024.04.17
백준 가계부 (0)	2024.04.10
백준 쵯소값과 최댓값 (0)	2024.04.08
백준 구간 합 구하기 (0)	2024.04.04

백준 수열과 쿼리 37

컴퓨터과학 2024. 7. 15. 01:12

2024. 7. 15. 01:12

https://www.acmicpc.net/problem/18436

요즘 계속 회사 일이 바빠기도 했고 집에서 조금 쉬다보니 공부를 못했던것 같습니다.

오랜만에 푸는거라 시간이 조금 많이 걸렸네요 ㅠ

package test01;
import java.util.*;
import java.io.*;
public class Main {
	public static int n;
	public static int m;
	public static int k;
	public static long tree[];
	

	public static long buildingTree(int start ,int end, int node, long arr[]){
	
		if(start==end){
			if(arr[start]%2==0) {
				return tree[node]=1;
			}else {
				return  tree[node]=0;
			}
			
		}

		int mid=(start+end)/2; // 0+5 =2

		return tree[node]=buildingTree(start, mid,node*2,arr)+buildingTree(mid+1,end,node*2+1,arr);
		
	}

	public static long updateTree(int start,int end,int node,long newValue, int findIndex){
	
		if(findIndex<start||findIndex>end){
			return tree[node];
		}
		

		if(start==end){
			if(newValue % 2 == 0) {
				return tree[node] = 1;
			} else {
				return tree[node] = 0;
			}
		}
		
		

		int mid=(start+end)/2;

		return tree[node]=updateTree(start,mid,node*2,newValue,findIndex)+updateTree(mid+1,end,node*2+1,newValue,findIndex);
		

	}

	public static long select (int start,int end,int node,int left,int right){
	
		if(left>end||right<start){
			return 0;
		}
		

		if(left<=start&&end<=right){
			return tree[node];
		}
		
		int mid=(start+end)/2;

		return select(start,mid,node*2,left,right)+select(mid+1,end,node*2+1,left,right);
		

	}

	public static void main(String[] args) throws Exception {
		Scanner scan = new Scanner(System.in);
		 n =scan.nextInt();
		 long arr[]=new long[n];
		 for(int t=0;t<n;t++){
				long tmp=scan.nextLong();
				arr[t]=tmp;
		}
		 
		 m=scan.nextInt();
	
		tree=new long[n*4];
		
		buildingTree(0,n-1,1,arr);
	
		for(int t=0;t<m;t++){
			int a=scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();
			if(a==1){
				//update
				if(arr[ b-1 ] %2 ==1 && c%2==0 ) {
					updateTree(0,n-1,1, c , b-1);
				}else if(arr[  (b-1) ] %2 ==0 && c%2==1 ){
					updateTree(0,n-1,1 ,c, b-1);
				}
				arr[b-1]=c;
				
			}else if(a == 2){
				// select
				long query = select(0, n - 1, 1, b - 1, c - 1);
				System.out.println(query);
			} else if(a == 3){
				// select
				long query = select(0, n - 1, 1, b - 1, c - 1);
				System.out.println((c - b + 1) - query);
			}
		}
	

	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 - 구간 합 구하기2 (0)	2024.07.17
백준 커피숍2 (0)	2024.04.17
백준 가계부 (0)	2024.04.10
백준 쵯소값과 최댓값 (0)	2024.04.08
백준 구간 합 구하기 (0)	2024.04.04

백준 커피숍2

컴퓨터과학 2024. 4. 17. 00:00

2024. 4. 17. 00:00

https://www.acmicpc.net/problem/1275

1275번: 커피숍2

첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합

www.acmicpc.net

쉽네여~

import java.util.*;
import java.io.*;
public class Main {
	public static long tree[];

	public static long buildingTree(int start,int end ,int node, long arr[]){
		if(start==end){
			return tree[node]=arr[start];
		}
		int mid=(start+end)/2;
		return tree[node]=buildingTree(start,mid,node*2,arr)+buildingTree(mid+1,end,node*2+1,arr);
	}

	public static void update( int start, int end, int node, long newValue, int findIndex){
		if(  end < findIndex  || findIndex < start){
			return;
		}

		if(start==end){
			tree[node]=newValue;
			return;
		}

		int mid=(start+end)/2;

		update( start, mid,node*2, newValue, findIndex);

		update(mid+1, end,node*2+1, newValue, findIndex);

		tree[node]=tree[node*2]+tree[node*2+1];
	}

	public static long select(int start ,int end, int node, int left, int right){
		if( left > end|| right < start ){
			return 0;
		}

		if( left<= start && end<=right ){
			return tree[node];
		}

		int mid=(start+end)/2;
		return select(start,mid,node*2,left,right)+select(mid+1,end,node*2+1,left,right);
	}

	public static void main(String[] args) throws Exception {
		Scanner scan = new Scanner(System.in);
		int n=scan.nextInt();
		int m=scan.nextInt();
		long arr[]=new long[n];
		tree=new long[n*4];
		for(int i=0;i<n;i++){
			long tmp=scan.nextLong();
			arr[i]=tmp;
		}
		buildingTree(0,n-1,1,arr);

		for(int i=0; i<m; i++ ){
			int x=scan.nextInt();
			int y=scan.nextInt();
			int a=scan.nextInt();
			long b=scan.nextLong();
			if(x>y){
				int tmp=y;
				y=x;
				x=tmp;
			}
			long sum=select(0,n-1,1,x-1,y-1);
			update(0,n-1,1, b,a-1);
			System.out.println(sum);
		}

	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 - 구간 합 구하기2 (0)	2024.07.17
백준 수열과 쿼리 37 (2)	2024.07.15
백준 가계부 (0)	2024.04.10
백준 쵯소값과 최댓값 (0)	2024.04.08
백준 구간 합 구하기 (0)	2024.04.04

백준 가계부

컴퓨터과학 2024. 4. 10. 19:44

2024. 4. 10. 19:44

https://www.acmicpc.net/problem/12837

12837번: 가계부 (Hard)

살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려

www.acmicpc.net

쉽네요 ~ 세그먼트 트리 문제

시간 초과되는 부분만 조심해주면 됩니다.

package test01;
import java.util.*;
import java.io.*;
import java.lang.*;
import java.io.*;
public class Main {
	
	public static long tree[];
	
	public static long buildTree(int start, int end , int node , long arr[]) {
		
		if(start==end) {
			return tree[node]=arr[start];
		}
		
		int mid=(start+end)/2;
		
		return tree[node]=buildTree(start,mid,node*2 ,arr)+ buildTree(mid+1,end,node*2+1,arr) ;
		
	}
	public static long select(int start, int end , int node, long left, long right) {
		 if (start > right || end < left) {
	            return 0;
	        }
	        if (start >= left && end <= right) {
	            return tree[node];
	        }
		
		int mid=(start+end)/2;
		
		return   select(start,mid,node*2 ,left, right)+ select(mid+1,end,node*2+1 ,left, right) ;
	}
	
	public static void update(int start, int end , int node, long newValue,long findIndex) {
		   if (start > findIndex || end < findIndex) {
	            return;
	        }
	        if (start == end) {
	            tree[node] += newValue;
	            return;
	        }
			int mid=(start+end)/2;
			
		
			update(start,mid,node*2 ,newValue, findIndex);
			update(mid+1,end,node*2+1 ,newValue, findIndex);
			tree[node]= tree[node*2] + tree[node*2+1];
		
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder bz= new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        long arr[] = new long[n];
        tree = new long[n * 4];

        int m = Integer.parseInt(st.nextToken());
      
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            long c = Long.parseLong(st.nextToken());
            if (a == 1) {
                update(0, n - 1, 1, c, b - 1);
            } else {
                long mins = select(0, n - 1, 1, Math.min(b, c) - 1, Math.max(b, c) - 1);
               
                System.out.println(mins);
            }
        }
	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 수열과 쿼리 37 (2)	2024.07.15
백준 커피숍2 (0)	2024.04.17
백준 쵯소값과 최댓값 (0)	2024.04.08
백준 구간 합 구하기 (0)	2024.04.04
백준 - 감시 (0)	2024.04.04

백준 쵯소값과 최댓값

컴퓨터과학 2024. 4. 8. 23:16

2024. 4. 8. 23:16

https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100

www.acmicpc.net

세그먼트 트리 알고리즘 기본 문제 중 하나입니다.

import java.util.*;
import java.io.*;
public class Main {

	public static long mintree[];
	public static long maxtree[];



	public static long minselect(int start,int end,int node,long left,long right){
		if(end<left||start>right){
			return Long.MAX_VALUE;
		}
		if(right>= end && left <= start){//5>=4 && 1<=0

			return mintree[node];
		}
		int mid=(start+end)/2;
		return Math.min( minselect(start,mid,node*2,left,right), minselect(mid+1,end,node*2+1,left,right));
	}

	public static long MinbuildingTree(int start,int end, int node, long arr[]){
		if(start==end){
			return mintree[node]=arr[start];
		}
		int mid=(start+end)/2;


		return mintree[node]=Math.min(MinbuildingTree(start,mid,node*2,arr), MinbuildingTree(mid+1,end,node*2+1,arr) );
	}

	public static long MaxbuildingTree(int start,int end, int node, long arr[]){
		if(start==end){
			return maxtree[node]=arr[start];
		}
		int mid=(start+end)/2;
		return maxtree[node]=Math.max(MaxbuildingTree(start,mid,node*2,arr), MaxbuildingTree(mid+1,end,node*2+1,arr) );
	}

	public static long maxselect(int start,int end,int node,long left,long right){
		if(end<left||start>right){
			return 0;
		}
		if(right>= end && left <= start){//5>=4 && 1<=0

			return maxtree[node];
		}
		int mid=(start+end)/2;
		return Math.max( maxselect(start,mid,node*2,left,right), maxselect(mid+1,end,node*2+1,left,right));
	}


	public static void main(String[] args) throws Exception {
		Scanner scan = new Scanner(System.in);
		int n=scan.nextInt();
		int m=scan.nextInt();
		long arr[]=new long[n];
		mintree=new long[n*4];
		maxtree=new long[n*4];
		for(int i=0;i<n;i++){
			long tmp=scan.nextLong();
			arr[i]=	tmp;
		}
		
		MinbuildingTree(0,n-1,1,arr);
		MaxbuildingTree(0,n-1,1,arr);

		for(int i=0;i<m;i++){
			long left=scan.nextLong()-1;
			long right=scan.nextLong()-1;
			long mins=minselect(0,n-1,1,left,right);
			long maxs=maxselect(0,n-1,1,left,right);
			System.out.println(mins+" "+maxs);
		

		}
	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 커피숍2 (0)	2024.04.17
백준 가계부 (0)	2024.04.10
백준 구간 합 구하기 (0)	2024.04.04
백준 - 감시 (0)	2024.04.04
백준 배열과 연산 (0)	2024.04.04

백준 구간 합 구하기

컴퓨터과학 2024. 4. 4. 21:32

2024. 4. 4. 21:32

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

세그먼트 트리 알고리즘 기본 문제

import java.util.*;
import java.io.*;
public class Main {
	public static int n;
	public static int m;
	public static int k;
	public static long tree[];
	public static void initTree(long arr[]){
		builingTree(0,n-1,1,arr);
	}

	public static long builingTree(int start ,int end, int node, long arr[]){
		//System.out.println("node:"+node+",start:"+start+",end:"+end);
		if(start==end){
			return tree[node]=arr[start];
		}

		int mid=(start+end)/2; // 0+5 =2

		return tree[node]=builingTree(start, mid,node*2,arr)+builingTree(mid+1,end,node*2+1,arr);
	}

	public static void updateTree(int start,int end,int node,long newValue, long findIndex){
		//System.out.println("node:"+node+",start:"+start+",end:"+end);
		if(findIndex<start||findIndex>end){
			return;
		}

		if(start==end){
			tree[node]=newValue;
			return;
		}

		int mid=(start+end)/2;

		updateTree(start,mid,node*2,newValue,findIndex);
		updateTree(mid+1,end,node*2+1,newValue,findIndex);
		tree[node]=tree[node*2]+tree[node*2+1];
	}

	public static long select (int start,int end,int node,long left,long right){
		//System.out.println("node:"+node+",start:"+start+",end:"+end);
		//System.out.println("left:"+left+",right:"+right);
		if(left>end||right<start){
			//System.out.println("zero");
			return 0;
		}

		if(left<=start&&end<=right){
			//System.out.println("sum:");
			return tree[node];
		}

		int mid=(start+end)/2;

		return select(start,mid,node*2,left,right)+select(mid+1,end,node*2+1,left,right);
	}

	public static void main(String[] args) throws Exception {
		Scanner scan = new Scanner(System.in);
		 n =scan.nextInt();
		 m=scan.nextInt();//change
		 k=scan.nextInt();//sum ?
		int ending=n+m+k+1;
		long arr[]=new long[n];
		for(int t=0;t<n;t++){
			long tmp=scan.nextLong();
			arr[t]=tmp;
		}
		tree=new long[n*4];
		builingTree(0,n-1,1,arr);
		//System.out.println();
		//for(int i=0;i<tree.length;i++){
		//	System.out.print(tree[i]+",");
		//}
		//System.out.println();
		//int query=select(0,n-1,1,0,1);
		//System.out.println("query:"+query);


		for(int t=0;t<(k+m);t++){
			int a=scan.nextInt();
			long b=scan.nextLong();
			long c=scan.nextLong();
			if(a==1){
				//update
				updateTree(0,n-1,1,c, b-1);
				//System.out.println();
				//for(int i=0;i<tree.length;i++){
					//System.out.print(tree[i]+",");
				//}
				//System.out.println();
			}else if(a==2){
				//select
				//b ~ c
				long query=select(0,n-1,1,b-1,c-1);
				System.out.println(query);
			}
		}

		// N+M+K+1 5 +2 +2 +1
		//a, b, c
		//a 1 -> (b->c)
		//a 2->(b~c sum)


	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 가계부 (0)	2024.04.10
백준 쵯소값과 최댓값 (0)	2024.04.08
백준 - 감시 (0)	2024.04.04
백준 배열과 연산 (0)	2024.04.04
백준 마법사 상어와 파이어스톰 (1)	2024.04.03

백준 - 감시

컴퓨터과학 2024. 4. 4. 00:53

2024. 4. 4. 00:53

https://www.acmicpc.net/problem/15683

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

음 어렵네요 개인적으로는 골3정도? 난이도네요

키포인트는 카메라들을 전부 모아서 방향으로 볼때의 경우의수를 전부 구해주면 해결은 됩니다.

1번 카메라 4방향, 2번 카메라 4방향 ... 5번 카메라 4방향의 모든 경우의수를 따져주면 해결됩니다.

사각지대는 카메라가 못본곳이라고 생각하면됩니다.

import java.util.*;
import java.io.*;
import java.lang.*;
import java.io.*;
public class Main {
	public static int maps[][];
	
	public static boolean bCheck[][];
	public static boolean bdir[];
	public static int n;
	public static int m;
	public static ArrayList<Camera>cameras=new ArrayList<>();
	public static class Camera{
		public int i;
		public int j;
		public int kind;
		public int dir=0;
		public Camera(int i,int j, int kind,int dir) {
			this.i=i;
			this.j=j;
			this.kind=kind;
			this.dir=dir;
		}
	}
	public static ArrayList<Integer>save=new ArrayList<>();
	
	
	
	
	public static void cameraSee(int ci,int cj,int dir) {
		dir=dir%4;
		switch(dir) {
			case 0:
				//n
				for(int i=0;i<n;i++) {
					ci=ci-1;
					if(ci < 0) {
						break;
					}
					
					if(bCheck[ci][cj]==true) {
						break;
					}
					if(maps[ci][cj]!=0) {
						continue;
					}
					maps[ci][cj]=9;
				}
				break;
			case 1:
				//e
				
				for(int i=0;i<m;i++) {
					cj=cj+1;
					
					if(cj > m -1) {
						break;
					}
					
					if(bCheck[ci][cj]==true) {
						break;
					}
					if(maps[ci][cj]!=0) {
						continue;
					}
					maps[ci][cj]=9;
				}
				break;
			case 2:
				//s
				for(int i=0;i<n;i++) {
					ci=ci+1;
					
					if(ci > n-1) {
						break;
					}
					
					if(bCheck[ci][cj]==true) {
						break;
					}
					if(maps[ci][cj]!=0) {
						continue;
					}
					maps[ci][cj]=9;
				}
				break;
			case 3:
				//w
				for(int i=0;i<m;i++) {
					cj=cj-1;
					if(cj < 0 ) {
						break;
					}
					
					if(bCheck[ci][cj]==true) {
						break;
					}
					if(maps[ci][cj]!=0) {
						continue;
					}
					maps[ci][cj]=9;
				}
				
				break;
				default:
					break;
		}
		
		
		
	}
	public static void Prints() {
		System.out.println();
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				
				System.out.print(maps[i][j]);
			}
			System.out.println();
		}
		System.out.println();
	}
	public static int mins=-1;
	public static void backtracking(int cnt) {
		
		if(cnt>=cameras.size()) {
			//Prints();
			int sum=0;
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(maps[i][j]==0) {
						sum++;
					}
				}	
			}
			
			if(mins==-1) {
				mins=sum;
			}else {
				mins=Math.min(sum,mins);
			}
			
			//System.out.println("find");
			return;
		}
		
		int initmaps[][] =new int[n][m];
		//System.out.println(cnt);
		//System.out.println(cameras.size());
		
		int ci=cameras.get(cnt).i;
		int cj=cameras.get(cnt).j;
		
		for(int d=0;d<4;d++) {
			
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					initmaps[i][j]=maps[i][j];
				}
			}
			
			int kind=cameras.get(cnt).kind;
			
			switch(kind) {
			//camera kinds
				case 1:
				//	System.out.println(ci+","+cj+","+d);
					cameraSee(ci,cj,d);
					break;
				case 2:
					cameraSee(ci,cj,d);
					cameraSee(ci,cj,d+2);
					break;
				case 3:
					cameraSee(ci,cj,d);
					cameraSee(ci,cj,d+1);
					break;
				case 4:
					cameraSee(ci,cj,d);
					
					cameraSee(ci,cj,d+1);
					cameraSee(ci,cj,d+3);
					break;
				case 5:
					cameraSee(ci,cj,d);
					cameraSee(ci,cj,d+1);
					cameraSee(ci,cj,d+2);
					cameraSee(ci,cj,d+3);
					break;
				default:
					break;
			}
			
			backtracking(cnt+1);
			
			
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					maps[i][j]=initmaps[i][j];
				}
			}
			
		}
	}
	public static void main(String[] args) throws Exception {
		Scanner scan = new Scanner(System.in);
		n =scan.nextInt();
		m =scan.nextInt();
		
		maps=new int[n][m];
		bCheck=new boolean[n][m];
		bdir=new boolean[4];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				int tmp=scan.nextInt();
				
				maps[i][j]=tmp;
				
				if(tmp==6) {
					bCheck[i][j]=true;
				}
				if(tmp!=0) {
					
					if(tmp!=6) {
						cameras.add(new Camera(i,j,tmp,-1));
					}
				}
			}
		}
		backtracking(0);
		
		System.out.println(mins);
		
		
		

	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 쵯소값과 최댓값 (0)	2024.04.08
백준 구간 합 구하기 (0)	2024.04.04
백준 배열과 연산 (0)	2024.04.04
백준 마법사 상어와 파이어스톰 (1)	2024.04.03
백준 마법사 상어와 토네이도 (0)	2024.04.02

백준 배열과 연산

컴퓨터과학 2024. 4. 4. 00:51

2024. 4. 4. 00:51

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

www.acmicpc.net

골드 4치곤 제법 쉬웠던 문제네요

import java.util.*;
import java.io.*;
public class Main {
	public static int matrix[][];
	public static int copyMatrix[][];
	public static int r;
	public static int c;
	public static int n;
	public static int m;
	public static int k;

	public static class Data{
		public int index;
		public int cnt;
		public Data(int index,int cnt){
			this.index=index;
			this.cnt=cnt;
		}
	}
	public static boolean Checking(int [][]matrix,int cnt){
		for(int i=0;i<matrix.length;i++){
			for(int j=0;j<matrix[i].length;j++){
				if(r==i&&c==j){
					if(matrix[r][c]==k){
						//System.out.println();
						System.out.println(cnt);
						return true;
					}
				}
			}
		}
		return false;
	}
	public static void PrintMatrix(int [][]matrix){
		System.out.println();
		for(int i=0;i<matrix.length;i++){
			for(int j=0;j<matrix[i].length;j++){
				System.out.print(matrix[i][j]+",");
			}
			System.out.println();
		}
		System.out.println();
	}
	public static void PrintData(ArrayList<Data>datas){
		for(int i=0;i<datas.size();i++){
			System.out.print("["+datas.get(i).index+","+datas.get(i).cnt+"]"+",");
		}
		System.out.println();

	}
	public static ArrayList<Data> Sorting(ArrayList<Data>datas){
		Collections.sort(datas,  new Comparator<Data>() {
			@Override
			public int compare(Data d1, Data d2) {
				if(d1.cnt>d2.cnt){
					return 1;
				}else if(d1.cnt==d2.cnt){
					if(d1.index>d2.index){
						return 1;
					}else{
						return -1;
					}

				}else if(d1.cnt < d2.cnt){
					return -1;
				}
				return 0;
			}
		});

		return datas;
	}

	public static boolean MakeMatrix(ArrayList<ArrayList<Integer>>gdatas , boolean bRow ,int cnts){
		int imaxs=0;
		int jmaxs=0;
		for(int i=0;i<gdatas.size();i++){
			imaxs=Math.max(gdatas.size(),imaxs);
			for(int j=0;j<gdatas.get(i).size();j++){
				jmaxs=Math.max(gdatas.get(i).size(),jmaxs);
			}

		}
	//	System.out.println("imaxs:"+imaxs+","+"jmaxs"+jmaxs); //3 6

		if(bRow==true){
			matrix=new int[imaxs][jmaxs];
			n=imaxs;
			m=jmaxs;
		}else{
			matrix=new int[jmaxs][imaxs];
			n=jmaxs;
			m=imaxs;
		}

		for(int i=0;i<gdatas.size();i++){
			for(int j=0;j<gdatas.get(i).size();j++){
				//0 0  0 0
				//1 0  0 1
				// 2 0  0 2
				if(bRow==true){
					matrix[i][j]=gdatas.get(i).get(j);
				}else{
					matrix[j][i]=gdatas.get(i).get(j);
				}

			}
		}
		// PrintMatrix(matrix);
		 return Checking(matrix,cnts);
	}

	public static boolean RowCalculate(boolean bRow,int cnts){
		//row sort
		//System.out.println();
		ArrayList<ArrayList<Integer>>gdatas=new ArrayList<>();
		//System.out.println(n+","+m);
		for(int i=0;i<n;i++){
			ArrayList<Data>datas=new ArrayList<>();

			for(int j=0;j<m;j++){
				int tmp=matrix[i][j];
				boolean bCheck=false;

				for(int s=0;s<datas.size();s++){
					if(datas.get(s).index==tmp&&tmp!=0){
						bCheck=true;
						int tmpcnt=datas.get(s).cnt;
						datas.get(s).cnt=tmpcnt+1;
						break;
					}

				}
				if(bCheck==false&&tmp!=0){
					datas.add(new Data(tmp,1));
				}

			}


			//sorting
			//ArrayList<Data> tmpdatas=new ArrayList<>();
			Sorting(datas);
			//makematrix
			//PrintData(datas);

			ArrayList<Integer>tmpDatas=new ArrayList<>();

			for(int s=0;s<datas.size();s++){

				tmpDatas.add(datas.get(s).index);
				tmpDatas.add(datas.get(s).cnt);
			}
			gdatas.add(tmpDatas);

			//System.out.println();
		}

		return 	MakeMatrix(gdatas,bRow,cnts);

	}
	public static boolean ColumCalculate(boolean bRow,int cnts){
		//row sort

		ArrayList<ArrayList<Integer>>gdatas=new ArrayList<>();

		for(int i=0;i<m;i++){
			ArrayList<Data>datas=new ArrayList<>();

			for(int j=0;j<n;j++){
				int tmp=matrix[j][i];
				boolean bCheck=false;

				for(int s=0;s<datas.size();s++){
					if(datas.get(s).index==tmp&&tmp!=0){
						bCheck=true;
						int tmpcnt=datas.get(s).cnt;
						datas.get(s).cnt=tmpcnt+1;
						break;
					}

				}
				if(bCheck==false&&tmp!=0){
					datas.add(new Data(tmp,1));
				}

			}


			//sorting
			//ArrayList<Data> tmpdatas=new ArrayList<>();
			Sorting(datas);
			//makematrix
			//PrintData(datas);

			ArrayList<Integer>tmpDatas=new ArrayList<>();

			for(int s=0;s<datas.size();s++){

				tmpDatas.add(datas.get(s).index);
				tmpDatas.add(datas.get(s).cnt);
			}
			gdatas.add(tmpDatas);

			//System.out.println();
		}

		return MakeMatrix(gdatas,bRow,cnts);

	}

	public static void main(String[] args) throws Exception {
		Scanner scan = new Scanner(System.in);
		 r=scan.nextInt()-1;
		 c=scan.nextInt()-1;
		 k=scan.nextInt(); //anw
		n=3;
		m=3;

		matrix=new int[n][m];
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				matrix[i][j]=scan.nextInt();
			}
		}

		boolean bCheck= Checking(matrix,0);
		//System.out.println(r+","+c);
		for(int i=1;i<=100;i++){
			if(bCheck==true){

				break;
			}
			if(n>=m){
				//r cal
				bCheck=RowCalculate(true,i);
			}else{
				//c cal
				bCheck=ColumCalculate(false,i);
				//ColumCalculate();
			}
		}
		if(bCheck==false){
			System.out.println(-1);
		}

	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 구간 합 구하기 (0)	2024.04.04
백준 - 감시 (0)	2024.04.04
백준 마법사 상어와 파이어스톰 (1)	2024.04.03
백준 마법사 상어와 토네이도 (0)	2024.04.02
백준 최소 회의실 개수 (0)	2024.04.02

PREV 이전 1 2 3 4 ···28 NEXT 다음

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

뚭