dp[i][j] < i 번째 집 j색깔 색깔이 0인 경우 이전 집 dp[i-1][1]과 dp[i-1][2] 중 더 비용이 적은 것에서 현재 0을 칠하는 비용을 더해주는 방식으로 갱신해준다. n번째 집까지 다 칠한 경우 dp[n-1][0], dp[n-1][1], dp[n-1][2] 중에서 가장 비용이 적은 것을 출력해준다. import java.util.Scanner; public class Main { static int n; static int[][] rgb; static int[][] dp; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); rgb=new int[n][3]; dp=new ..
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 보자마자 dfs 풀이가 생각났으나 dp로 풀어보려고 했다. a,b,c 대신에 배열을 쓰면 좀 더 깔끔할 듯하다. 최종 dp[n]에 들어가는 수가 1로 시작해서 n을 만들 수 있는 경우의 수이니 n에서 1을 만드는 것과 방법의 수가 같다. 각각의 방법으로 현재 수 i를 만드는 방법 중 최소의 계산 횟수를 넣어준다. import java.util.Arrays; import java.util.Scanner; public class Main { static int answer; static int n; static int[] dp;..
www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net import java.util.PriorityQueue; import java.util.Scanner; class edge implements Comparable{ int s; int e; int w; public edge(int s, int e, int w) { super(); this.s = s; this.e = e; this.w = w; } @Override ..
먼저 union-find 알고리즘으로 그룹을 연결해준다. vis배열 (해당 집합 그룹을 방문했는지)를 만든 다음 1번부터 n번까지 체크해준다. 이미 앞에서 방문한 집합에 속한 번호라면 pass 방문했던 집합에 속하지 않은 번호라면 1. 먼저 친구비를 내서 사귈 수 있는 친구인지 확인한다. 2. 해당 번호가 속한 집합의 vis를 true로 해주고 방문한 번호의 개수(cnt)를 1 증가시킨다. 3. 낸 비용만큼 answer를 증가시킨다. import java.util.Scanner; //친구비 public class B_16562_Main { static int n,m,k; static int[] money; public static void main(String[] args) { Scanner sc=new..
www.acmicpc.net/problem/13300 13300번: 방 배정 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 < K ≤ 1,000)가 공백으로 분리되어 www.acmicpc.net import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int k=sc.nextInt(); int[] girls=new int[7]; in..
www.acmicpc.net/problem/2804 2804번: 크로스워드 만들기 A의 길이를 N, B의 길이를 M이라고 했을 때, 출력은 총 M줄이고, 각 줄에는 N개 문자가 있어야 한다. 문제 설명에 나온 것 같이 두 단어가 교차된 형태로 출력되어야 한다. 나머지 글자는 '.'로 출력 www.acmicpc.net import java.util.Scanner; //2804번 public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String a=sc.next(); String b=sc.next(); int n=0,m=0; for (int i = 0; i < a.length(); i++) ..
www.acmicpc.net/problem/2567 2567번: 색종이 - 2 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net import java.util.Scanner; public class Main { static int n; static int[][] map; static int[] xpos= {0,0,1,-1}; static int[] ypos= {1,-1,0,0}; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextIn..
import java.util.Scanner; public class Main { static int n; static int[][] map; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); map=new int[101][101]; for (int k = 0; k = c; i--) { for (int j = r; j < r+width; j++..
www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 알파벳을 0~25의 숫자로 바꿔서 boolean체크를 해준다 import java.util.Scanner; public class Main { static int r,c; static String map[]; static int[] xpos= {0,0,1,-1}; static int[] ypos= {1,-1,0,0}; static int ans=Integer.MIN_VALUE; static boolean..
www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 중간에 아니면 다른 경우를 탐색한다. 혹은 그만둔다. (백트래킹) 파이프를 가장 많이 연결하려면 최대한 위쪽으로 연결한다. 연결이 하나라도 되면 다른 경우는 생각하지 않고 다음 열에서 파이프라인을 연결을 시작한다. import java.util.Scanner; public class Main { static int r,c; static int map[][]; static boolean vis[][]; static int xpo..