6-6화이탱

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹을 사용하여 해결하면 된다. 연속되는 숫자중에 같은 부분이 있는지 확인하며 수열을 만들어나간다. 제일 작은 수열이므로 가장 먼저 만들어질 것이기에 수열의 길이가 n일 경우 프로그램을 종료시킨다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { stat..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net index보다 작은 제곱수의 최소합을 확인하여 구해나가면 된다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Number..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net bfs를 이용하여 문제를 해결할 수 있었다. 일차원 배열을 생성하여 index번호에 도달할 수 있는 시간을 저장한다. 따라서 예시에서 수빈이의 위치는 5이고, 동생의 위치는 17이다. 그럼 dp[5]는 0초이다. 그러나 계산하기 쉽게 1로 세팅해준다. 그리고 dp[5-1] , dp[5+1], dp[5*2] 는 1초이다. 계산하기 쉽도록 dp[5]+1을 한다. 만약, 이미..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp[n+1][3] dp[n][0] -> n행의 0열은 n행에 아무것도 넣지 않았을때를 뜻함 dp[n][1] -> n행의 1열은 1번째 열에 사자를 넣을 경우의 수를 뜻함 dp[n][2] -> n행의 2열은 2번째 열에 사자를 넣을 경우의 수를 뜻함 따라서 점화식은 dp[n][0] = dp[n-1][0] + dp[n-1][1]+ dp[n-1][2] : 아무것도 넣지 않았을 경우에는 다른 열의 영향이 없기 떄문에 이전 행의 모든 경우의 수를 합한 값이 된다. dp[n][1] = dp[n-1][0]+dp[n-1][2] : 1번째 열에..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 점화식 dp[j] = dp[j] + dp[j-i번째 동전값] dp[j]는 j원이 될 수 있는 경우의 수를 뜻한다. 1) i=1 dp[1]=dp[1]+dp[1-1]; -> 1 dp[2]=dp[2]+dp[1]; -> 1 . . dp[10]=dp[10]+dp[10-1]; ->1 2) i=2 dp[2]=dp[2]+dp[2-2]; -> 2 dp[3]=dp[3]+dp[3-2];->2 dp[4]=dp[4]+dp..

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net n=2 -> 3 n=4 -> 11 n=6 -> 41 점화식 : arr[i]= arr[i-1]*4 - arr[i-2] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new B..

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net split 함수를 사용하여 풀었다. StringTokenizer 로 0과 1을 구분하여 countTokens 가 작은 것으로 문제를 풀 수도 있다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(Str..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 우선순위 큐를 사용하여 이 문제를 해결할 수 있었다! 1. 무게와 가격을 가진 보석 객체를 생성하여 무게 오름차순 정렬한다. 2. 가방 무게 오름차순 정렬한다. 3. 가방 전체를 돌면서 해당하는 무게에 들어 갈 수 있는 보석의 가격을 우선순위 큐에 넣는다. ( 우선순위 큐는 내림차순정렬) import java.io.BufferedRead..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS를 사용하여 푸는 문제였다. 1. dot 클래스를 생성하여 익은 토마토가 있는 x,y좌표를 큐에 저장한다. 2. 큐의 값을 poll하여 동서남북으로 안익은 토마토가 있는지 확인한 후, 안익은토마토 위치에는 익은 일수를 넣어준다. ( 첫날 익었으면 1, 둘째날은 첫날 익은 토마토 위치의 값 +1 ...) 그리고 큐에 add 하고 큐가 비어질때까지 반복한다. 3. 모든 토마토가 ..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 해결법을 생각하기에는 쉬운 문제였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int n; static ..