백준63

• [Java] 백준 9465 : 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net card []에 가격을 넣어준다. 0번째 카드가 0 인 것은 나중에 최댓값 찾을 때를 위해 비워 둔 것이다. 0 50 10 100 20 40 0 30 50 70 10 60 이때 dp[][]에 각 해당하는 자리의 스티커를 떼어냈을 때의 최댓값을 더해 대입하면 된다. 해당 자리의 윗칸 스티커를 떼려면 직전에 아래칸 스티커를 떼었거나, 직전 아래칸 스티커는 떼지 않고 전전 아래칸 스티커를 떼.. 코딩테스트/백준 2023. 2. 9.

• [Java] 백준 11052 : 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net - 카드 i개가 들어 있는 카드팩 각 가격 price[] - 카드 N개를 구매하기 위한 최대금액 dp[] 아래처럼 진행이 되는데 여기서 규칙을 찾으면 된다. dp[0]=0, 1) 카드 한 장을 살 때 필요한 금액 dp[1]=price[1] =dp[0] + price[1] 2) 카드 두장을 살 때 필요한 금액 dp[2]=price[2] =dp[0] + price[2] dp[2]=price[1]*2 = dp.. 코딩테스트/백준 2023. 2. 8.

• 

  [Java] 백준 10844 : 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp [][]의 이차원 배열을 사용해서 사용하면 된다. dp [N][i]로 N은 몇 개짜리 계단인지를 의미하고, i는 가장 맨 앞의 자릿수가 i일 때를 의미한다. 이 내용을 그림으로 정리해봤다. dp [][]의 값 에는 해당 개수가 들어갈 예정이다. 예를 들어, dp [2][3]= 2 이렇게. 그러면 어떻게 이 값을 구하냐가 문제인데 간단하다. dp [2][3]일 때 만들 수 있는 계단은 3(N+1)과 3(N-1)이다. 즉, 34와 32이다. 하나의 계단이 추가되는 것이니까 dp [1][2]와 dp [1][4].. 코딩테스트/백준 2023. 2. 4.

• [Java] 백준 11729 : 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net import java.util.*; public class Main { static StringBuilder sb = new StringBuilder(); public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N=sc.nextInt(); /*하노이 횟수 구하는 공식 - hanoi(N)=hanoi.. 코딩테스트/백준 2023. 2. 4.

• [Java] 백준 1932 : 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택해서 더해가야 한다. 배열에는 아래처럼 저장되어 있다. 7 0 0 0 0 3 8 0 0 0 8 1 0 0 0 2 7 4 4 0 4 5 2 6 5 여기서 그래프의 대각선 왼쪽 또는 대각선 오른쪽은 배열에서 자신의 바로 위에 있는 수 혹은 자신의 왼쪽위에 있는 수 이다. 그래서 가장 왼쪽에 있는 수 즉, i=0인 경우 왼쪽 위는 존재 하지 않으므로 if(j==0) { arr[i][j]=arr[.. 코딩테스트/백준 2023. 2. 3.

• 

  [Java] 백준 1149 : RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 모든 집을 칠하는 최솟값을 구해야 한다. 규칙은 아래와 같다. 현재 칠할 집의 색은 앞에 칠해진 집의 색과 다르면 된다. 1. RGB 값을 각각 저장한 다음 dp[][]에 이전에 칠해진 색상을 제외한 비용 중 최솟값을 구한다. 2. dp[]에 누적 비용을 저장한다. dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+R; dp[i][1]=Math.min(.. 코딩테스트/백준 2023. 2. 1.

• 백준 2667 : 단지번호붙이기 _자바 Java https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net DFS를 사용하였다. 1. 단지별 아파트 개수 저장에 배열 사용. import java.io.*; import java.util.*; public class Main { static int N,cnt=0; static int[] apart; static int[][] arr; static boolean[][] check; static int[] dx = {0, 0, 1, -1}; static int.. 코딩테스트/백준 2023. 2. 1.

• 백준 2178 : 미로 탐색 _자바 Java https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 입력 받은 배열에서 (0,0)에서 다른 좌표로 이동했을 때 그 좌표까지 이동 했을 때 이동 거리를 대입. import java.io.*; import java.util.*; public class Main { static int N, M; static int[][] arr; static boolean[][] check; static int[] moveX = { 0, 0, 1, -1 }; static int[] moveY = { .. 코딩테스트/백준 2023. 1. 31.

• 백준 1406 : 에디터 _자바 Java https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 스택 두개를 선언을 해주고 커서가 왼쪽으로 움직이면 스택에 들어가 있는 문자를 오른쪽으로 옮겨주는 방식을 사용하여 문제 해결. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedRead.. 코딩테스트/백준 2023. 1. 31.

• 백준 2630 : 색종이 만들기 _자바 Java https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net check(시작X,시작Y,나눠진 크기) import java.io.*; import java.util.*; public class Main { static int[][] arr; static int white=0,blue=0; public static void main(String[] args) throws IOException{ BufferedReader br = ne.. 코딩테스트/백준 2023. 1. 30.

• 백준 11725 : 트리의 부모 찾기 _자바 Java https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt();//노드 개수 ArrayList[] list = new ArrayList[N+1]; boolean[] visit= new boolean[N+1]; int[] parent= new int[N+1]; for(int i=0;i 코딩테스트/백준 2023. 1. 29.

• 백준 18870 : 좌표 압축 _자바 Java https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); StringBuilder sb = new StringBuilder(); int cnt=0; int N = sc. nextInt(); int[.. 코딩테스트/백준 2023. 1. 29.