6-6화이탱

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 ..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 backtracking 의 대표적인 문제이다. 익숙하지 않은 기법이기에 문제 풀이하는데에 시간이 많이 소요되었다. 체스판에서 퀸은 가로 세로 대각선으로 무제한 이동 가능하다는 특징이 있다. 따라서 하나의 행에는 단 하나의 퀸만 놓을 수 있다!! 이 점을 토대로 일차원배열을 생성하여 'arr[행] = 열' 로 확인해나가는 것이 핵심이다!!!! import java.io.BufferedReader; imp..