'NOTE/BAEKJOON' 카테고리의 글 목록

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.HashMap;
public class Test {
	static HashMap<Integer,ArrayList<Integer>> graph;
	static long[] dp = new long[300001];
	static long answer=0;
	static long N;
	public static void main(String[] args) throws IOException { 
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		graph = new HashMap<>();
		for(int i=1; i<=N; i++) graph.put(i,new ArrayList<>());
		
		for(int i=0; i<N-1; i++) {
			st = new StringTokenizer(br.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		makeRoute(1); //root(정상): 1
		bw.write(answer-numberOfCase2(N)+"\n");//루트노드가 중복되서 들어가기 때문에 전체 경우의 수 빼줌
		bw.flush();
		bw.close();
	}
	static long makeRoute(int i) {
		dp[i]=1;
		for(int node : graph.get(i)) {
			if(dp[node]==0) dp[i] += makeRoute(node);
		}
		
		//전체에서 노드 2개 선택 경우의 수 - 부모 노드 포함한 서브트리에서 2개 선택 경우의 수
		answer += numberOfCase2(N)-numberOfCase2(N-dp[i]);
		
		return dp[i];
	}
	static long numberOfCase2(long n) { //2개 선택하는 경우의 수 -> nC2
		return n*(n-1)/2;
	}
}

보고 풀어도 어렵네 ..😶‍🌫️

이게 초등부 문제라구요..? ..

'NOTE > BAEKJOON' 카테고리의 다른 글

9205 맥주 마시면서 걸어가기 (0)	2022.10.09
9084 동전 (0)	2022.10.08
14502 연구소 (1)	2022.09.30
2565 전깃줄 (0)	2022.03.21
11054 가장 긴 바이토닉 부분 수열 (0)	2022.03.21

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;
public class Test {
	static int N;
	static int x,y;
	static int distance = 1000; // 20*50
	static Point festival;
	static Point home;
	public static void main(String[] args) throws IOException { 
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int testCase=1; testCase<=T; testCase++) {
			N = Integer.parseInt(br.readLine()); //맥주 파는 편의점 개수

			//집
			st=new StringTokenizer(br.readLine()," ");
			x=Integer.parseInt(st.nextToken());
			y=Integer.parseInt(st.nextToken());
			home = new Point(x,y);
			//편의점 N개
			Point[] cvStores = new Point[N];
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				x=Integer.parseInt(st.nextToken());
				y=Integer.parseInt(st.nextToken());
				cvStores[i]=new Point(x,y);
			}
			//펜타포트 락 페스티벌
			st = new StringTokenizer(br.readLine());
			x=Integer.parseInt(st.nextToken());
			y=Integer.parseInt(st.nextToken());
			festival = new Point(x,y);
	
			bw.write((isHappyFestival(cvStores) ? "happy": "sad") + "\n");
		}
		bw.flush();
		bw.close();
	}
	
	static boolean isHappyFestival(Point[] cvStores) {
		
		boolean[] visited = new boolean[N];
		Queue<Point> q = new LinkedList<>();
		q.add(home);
		while(!q.isEmpty()) {
			Point p = q.poll();
			if(getDistance(p,festival)<= distance) return true;
		
			for(int i=0; i<N; i++) {
				if(!visited[i] && getDistance(p,cvStores[i])<=distance ) {
					visited[i] = true;
					q.add(cvStores[i]);
				}
			}
		}
		return false;
	}
	
	static int getDistance(Point p1, Point p2) {
		return Math.abs(p1.x-p2.x)+Math.abs(p1.y-p2.y);
	}
}
class Point{
	int x;
	int y;
	
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

'NOTE > BAEKJOON' 카테고리의 다른 글

20188 등산 마니아 (0)	2022.10.10
9084 동전 (0)	2022.10.08
14502 연구소 (1)	2022.09.30
2565 전깃줄 (0)	2022.03.21
11054 가장 긴 바이토닉 부분 수열 (0)	2022.03.21

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Test {
	static int[] dp;
	public static void main(String[] args) throws IOException{ 
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int testCase=1; testCase<=T; testCase++) {
			int N = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine()," ");
			int[] coins = new int[N+1];
			for(int i=1; i<=N; i++) {
				coins[i] = Integer.parseInt(st.nextToken());
			}
			int M = Integer.parseInt(br.readLine());
			dp = new int[M+1];
			dp[0]=1;
			
			for(int i=1; i<=N; i++) {
				for(int j=coins[i]; j<=M; j++) {
					dp[j]+=dp[j-coins[i]];
				}
			}
			bw.write(dp[M]+"\n");
		}
		bw.flush();
		bw.close();
	}	
}

<2원 동전으로 M원 만들기>

2원 동전으로 2원 만들기 -> 2 + 0

2원 동전으로 3원 만들기 -> 2 + 1

2원 동전으로 4원 만들기 -> 2 + 2

2원 동전으로 5원 만들기 -> 2 + 3

...

dp[M] += dp[M-2]

<3원 동전으로 M원 만들기>

3원 동전으로 3원 만들기 -> 3 + 0

3원 동전으로 4원 만들기 -> 3 + 1

3원 동전으로 5원 만들기 -> 3 + 2

...

dp[M] += dp[M-3]

...

< X원 동전으로 M원 만들기>

dp[M] += dp[M-X]

🏃‍♀️

'NOTE > BAEKJOON' 카테고리의 다른 글

20188 등산 마니아 (0)	2022.10.10
9205 맥주 마시면서 걸어가기 (0)	2022.10.09
14502 연구소 (1)	2022.09.30
2565 전깃줄 (0)	2022.03.21
11054 가장 긴 바이토닉 부분 수열 (0)	2022.03.21

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
public class Test {
	static int N,M;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,1,-1};
	static int answer = Integer.MIN_VALUE;
	public static void main(String[] args) throws IOException{ 
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N][M];
		
		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());
			}
		}
		
		makeWall(0,map);

		bw.write(answer+"\n");
		bw.flush();
		bw.close();
	}
	
	static void makeWall(int count,int[][] map) {
		if(count==3) {
			spreadVirus(map);
			return;
		}
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]==0) {
					map[i][j]=1;
					makeWall(count+1,map);
					map[i][j]=0;			
				}
			}
		}
	}
		
	static void spreadVirus(int[][] arr) {
		int[][] map = new int[N][M]; //새로운 map
		
		Queue<Point> q = new LinkedList<>();
		
		//바이러스 q에 넣기
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j]=arr[i][j];
				if(map[i][j]==2) {
					q.add(new Point(i,j));
				}
			}
		}
		//2면 바이러스 상하좌우로 퍼뜨리기
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = p.x + dx[i];
				int ny = p.y + dy[i];
				
				if( nx<0 || ny<0 || nx>=N || ny>=M || map[nx][ny]!=0) continue;
				
				map[nx][ny] = 2;
				q.add(new Point(nx,ny));
			}
		}
		//안전 구역 세기
		answer = Math.max(answer,countSafeArea(map));
	}
	
	static int countSafeArea(int[][] map){
		int count =0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]==0) {
					count++;
				}
			}
		}
		return count;
	}	
}

class Point{
	int x;
	int y;
	
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

바이러스를 뿌릴 때 복사 배열을 하나 만들어서 해야하는 걸 생각하지 못했다

으이9 . .. 😶‍🌫️

'NOTE > BAEKJOON' 카테고리의 다른 글

9205 맥주 마시면서 걸어가기 (0)	2022.10.09
9084 동전 (0)	2022.10.08
2565 전깃줄 (0)	2022.03.21
11054 가장 긴 바이토닉 부분 수열 (0)	2022.03.21
11053 가장 긴 증가하는 부분 (0)	2022.03.21

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Comparator;
import java.util.Arrays;
public class main {
	static int[][] arr;
	static int[] dp;
	static int N;
	static int count=0;
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N+1][2];
		
		dp = new int[N+1];

		StringTokenizer st;
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			arr[i][0]=Integer.parseInt(st.nextToken());
			arr[i][1]=Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr,new Comparator<int[]>(){
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0]-o2[0];
			}
		});
		
		for(int i=1; i<=N; i++) {
			dp[i]=1;
			for(int j=1; j<=i; j++) {
				if(arr[i][1]>arr[j][1]) {
					dp[i] = Math.max(dp[i],dp[j]+1);
				}
			}
		}
		
		int max=Integer.MIN_VALUE;
		for(int i=1;i<=N;i++) {
			max=Math.max(max,dp[i]);
		}
		bw.write(N-max+"\n");
		bw.flush();
		bw.close();
		
    }
}

아,,, lcs 다 다시풀어봐야겠다,,

정렬해줌으로써 arr[][1] 값만 비교해주면된다 ,, [i][1] 보다 작은 애들이 겹치는 애들이라 제거해줘야 한다.

여기서 요구하는 건 최소값인데 max를 구했으므로 N에서 빼준다.

여집합 마냥,, ,,

dp 내게왕이ㅏㅏ아악

'NOTE > BAEKJOON' 카테고리의 다른 글

9084 동전 (0)	2022.10.08
14502 연구소 (1)	2022.09.30
11054 가장 긴 바이토닉 부분 수열 (0)	2022.03.21
11053 가장 긴 증가하는 부분 (0)	2022.03.21
2156 포도주 시식 (0)	2022.03.21

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class main {
	static int[] arr;
	static int[] dp;
	static int[] dp2;
	static int N;
	static int count=0;
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N+1];
		dp = new int[N+1];
		dp2 = new int[N+1];	
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for(int i=1; i<=N; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
			dp[i]=1;
			dp2[i]=1;
		}
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<i; j++) {
				if(arr[i]>arr[j]) dp[i] = Math.max(dp[i],dp[j]+1);
			}
		}
		
		for(int i=N; i>=1; i--) {
			for(int j=N; j>i; j--) {
				if(arr[i]>arr[j]) dp2[i] = Math.max(dp2[i],dp2[j]+1);
			}
		}
		
		int max=Integer.MIN_VALUE;
		
		for(int i=1;i<=N;i++) {
			max=Math.max(max,dp[i]+dp2[i]);
		}
		
		bw.write(max-1+"\n");
		bw.flush();
		bw.close();
		
    }
}

계속 틀렸다해서 그냥 풀이봤따 ! ^^

그냥 배열 하나 더만들어서 합쳐버리네요,, 천재들;;;;;;;;;;;;;;;;;;;

이게 두개 더해주는거니까 마지막에 1빼줘야한다

'NOTE > BAEKJOON' 카테고리의 다른 글

14502 연구소 (1)	2022.09.30
2565 전깃줄 (0)	2022.03.21
11053 가장 긴 증가하는 부분 (0)	2022.03.21
2156 포도주 시식 (0)	2022.03.21
10844 쉬운 계단 수 (0)	2022.03.20

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class main {
	static int[] arr;
	static int[] dp;
	static int N;
	static int count=0;
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N+1];
		dp = new int[N+1];
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for(int i=1; i<=N; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		dp[1]=1;
		
		for(int i=2; i<=N; i++) {
			dp[i]=1;
			for(int j=1;j<i;j++) {
				if(arr[i]>arr[j]) {
					dp[i]=Math.max(dp[i],dp[j]+1);
				}
			}
		}
		
		int max=Integer.MIN_VALUE;
		for(int i=1;i<=N;i++) {
			max = Math.max(dp[i],max);
		}
		
		bw.write(max+"\n");
		bw.flush();
		bw.close();
		
    }
}

LIS라고 해서,, 그냥 바로 풀이봤다 더 완벽히 이해해볼게요,,

'NOTE > BAEKJOON' 카테고리의 다른 글

2565 전깃줄 (0)	2022.03.21
11054 가장 긴 바이토닉 부분 수열 (0)	2022.03.21
2156 포도주 시식 (0)	2022.03.21
10844 쉬운 계단 수 (0)	2022.03.20
1463 1로 만들기 (0)	2022.03.19

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.InputStreamReader;
import java.io.IOException;

public class main {
   static int[] dp;
   static int[] score;
   static int N;
   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
       N = Integer.parseInt(br.readLine());
       dp= new int[N+1];
       score = new int[N+1];
       
       for(int i=1;i<=N; i++) {
          score[i]= Integer.parseInt(br.readLine());
       }
       
       if(N==1) {
          bw.write(score[1]+"\n");
           bw.flush();
           bw.close();
           return;
       }
       
       dp[1]=score[1];
       dp[2]=score[1]+score[2];
       
       for(int i=3;i<=N; i++) {
          dp[i] = Math.max(dp[i-1],Math.max(dp[i-2]+score[i],dp[i-3]+score[i]+score[i-1]));
       }
       
       bw.write(dp[N]+"\n");
       bw.flush();
       bw.close();
    }
}

바로 계단오르기 문제가 떠올랐다

그래서 전에 풀었던 방식으로 풀려고 했는데 테스트케이스는 맞는데 계속 틀렸다고 해서 보니까

0번 마신 경우를 고려안했다. 난 1번과 2번 마신 경우만 고려했던 것 ,,,,

근데 score 배열 쓰는게 훨 간단해서,, 방법을 바꿨다.. 다들 score배열 만들어서 하는 이유가 있었다 흑

'NOTE > BAEKJOON' 카테고리의 다른 글

11054 가장 긴 바이토닉 부분 수열 (0)	2022.03.21
11053 가장 긴 증가하는 부분 (0)	2022.03.21
10844 쉬운 계단 수 (0)	2022.03.20
1463 1로 만들기 (0)	2022.03.19
2579 계단 오르기 (0)	2022.03.18

nose딩

NOTE/BAEKJOON

20188 등산 마니아

'NOTE > BAEKJOON' 카테고리의 다른 글

9205 맥주 마시면서 걸어가기

'NOTE > BAEKJOON' 카테고리의 다른 글

9084 동전

'NOTE > BAEKJOON' 카테고리의 다른 글

14502 연구소

'NOTE > BAEKJOON' 카테고리의 다른 글

2565 전깃줄

'NOTE > BAEKJOON' 카테고리의 다른 글

11054 가장 긴 바이토닉 부분 수열

'NOTE > BAEKJOON' 카테고리의 다른 글

11053 가장 긴 증가하는 부분

'NOTE > BAEKJOON' 카테고리의 다른 글

2156 포도주 시식

'NOTE > BAEKJOON' 카테고리의 다른 글

+ Recent posts

티스토리툴바