nose딩

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;
	}
}

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

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

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;
	}
}

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]

🏃‍♀️

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 . .. 😶‍🌫️

class Solution {
    static int[] dp1;
    static int[] dp2;
    static int N;
    public int solution(int[] money) {
        N = money.length; 
        dp1 = new int[N+1];//첫 집 털기
        dp2 = new int[N+1];//첫 집 안 털기
        
        dp1[1]=money[0]; //첫 집 털기
        
        for(int i=2; i<=N; i++){
            dp1[i] = Math.max(dp1[i-2]+money[i-1],dp1[i-1]);
            dp2[i] = Math.max(dp2[i-2]+money[i-1],dp2[i-1]);
        }
        return Math.max(dp1[N-1],dp2[N]);
    }
}

class Solution {
    static int[][] dp;
    static int N;
    public int solution(int[][] triangle) {
        int answer = 0;
        N = triangle.length;
        dp = new int[N+1][N+1];

        for(int i=1; i<=N; i++){
            dp[i][1] = dp[i-1][0] + triangle[i-1][0]; //처음
            int M = triangle[i-1].length;
            for(int j=1; j<=M-1; j++){ //중간
                dp[i][j] = Math.max(dp[i-1][j-1],dp[i-1][j]) + triangle[i-1][j-1];
            }
            dp[i][M] = dp[i-1][M-1] + triangle[i-1][M-1]; //끝
        }
        
        for(int i=1; i<=N; i++){
            answer=  Math.max(answer,dp[N][i]); //바닥에서 큰 값
        }
        
        return answer;
    }
}

다시 푸니까 헷갈리네 .. .🥲

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] graph = new int[n+1][n+1];
        
        for(int[] i : results){
            graph[i[0]][i[1]]=1; //이긴 경우
        }
        //간접적 승패 업데이트 (A->B, B->C => A->C)
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                for(int z=1; z<=n; z++){
                    if(graph[j][i]==1 && graph[i][z]==1){
                        graph[j][z]=1;
                    }
                }
            }
        }
        //경기 횟수 카운트
        for(int i=1; i<=n; i++){
            int count = 0;
            for(int j=1; j<=n; j++){
                if(graph[i][j]==1 || graph[j][i]==1) count++;
            }
            if(count == n-1) answer++;
        }
        
        return answer;
    }
}

플로이드- 워셜 이용해야 하는 문제

코린이는 모르는게 넘 많습니다 ... 공부하자 아자🌱

*플로이드-워셜 : 모든 정점에서 모든 정점으로 가는 최단거리를 구할 수 있음

class Solution {
    static int[][] minDp;
    static int[][] maxDp;
    static int N;
    public int solution(String arr[]) {
        N = (arr.length/2)+1; //피연산자 개수
        minDp = new int[N][N];
        maxDp = new int[N][N];
        
        for(int i=N-1; i>=0; i--){
            for(int j=0; j<N; j++){
                if(i==j) { //피연산자 저장
                    maxDp[i][j] = minDp[i][j] = Integer.parseInt(arr[i*2]);
                }else{ 
                    maxDp[i][j] = Integer.MIN_VALUE; //초기화
                    minDp[i][j] = Integer.MAX_VALUE; //초기화
                    
                    for(int k=i; k<j; k++){ //i~j까지 계산
                        if(arr[2*k+1].equals("+")){
                            minDp[i][j] = Math.min(minDp[i][j],minDp[i][k]+minDp[k+1][j]);
                            maxDp[i][j] = Math.max(maxDp[i][j],maxDp[i][k]+maxDp[k+1][j]);
                        }else{ //'-' 경우
                            minDp[i][j] = Math.min(minDp[i][j],minDp[i][k]-maxDp[k+1][j]);
                            maxDp[i][j] = Math.max(maxDp[i][j],maxDp[i][k]-minDp[k+1][j]);
                        }
                    }
                }
            }
        }
        
        return maxDp[0][N-1];
    }
}

최댓값을 구하는 문제

=>최대가 나오기 위해선

+의 경우: 최대 + 최대

-의 경우: 최대 - 최소

따라서 최대, 최소를 다루는 각 dp 만들어주고

피연산자를 저장한다.

그외 부분은 정수 최소값, 최대값으로 초기화해준다.

완벽히 이해하고 싶다 아아아아아아 🥲