다이나믹 프로그래밍 문제입니다. 직선에 N개의 집이 설치되어 있습니다. 양 옆의 집과 다른 색으로 칠할 때 최소비용을 찾아야합니다. 맨 왼쪽집과 맨 오른쪽 집도 같으면 안됩니다. 맨 왼쪽과 맨 오른쪽이 달라야하므로 DP에 최소값을 채워나가면 최적의 값을 찾을 수 없습니다. 그래서 3가지로 나눠서 DP값을 채워나갑니다. 1. 빨강으로 출발한 경우 2. 파랑으로 출발한 경우 3. 노랑으로 출발한 경우 마지막까지 계산 한 후 가장 작은 값을 출력해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java..
시뮬레이션 문제입니다 PC방 요금을 최소한으로 냈을 때 금액을 출력해야합니다. 2가지 방법이 있습니다. 1. 1시간에 1000원 지불 2. 22:00 ~ 08:00 5000원 지불 10시~3시의 경우 남은시간이 5시간 이상이면 2번을 실행하고 그 외에는 전부 1번으로 진행해서 계산해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { public static void m..
N일 동안 전날과 다른 떡을 줄 수 있는지 찾는 문제입니다. 단순히 전날과 다른 떡을 주면 되므로 아래 두 경우는 같다고 볼 수있습니다. 1. 1 - 2 (1일에 1번떡, 2일에 2번떡) 2. 3 - 2 (1일에 3번떡, 2일에 2번떡) DFS로 모든 경우의 수를 확인해주었습니다. 중복된 과정이 많이 생기므로 방문배열을 만들어서 X일에 A떡을 주었다는 것을 기록합니다. 동일하게 X일에 A떡을 준 경우 이미 탐색했으므로 탐색하지 않습니다. 최종적으로 N일 동안 다 주었을때 준 떡을 순서대로 출력해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.O..
수열이 주어질때 규칙에 따라 등차수열로 변화시킬 수 있는지 찾는 문제입니다. 등차수열은 수열의 수의 앞뒤의 차가 전부 같은 수열을 말합니다. 수열이 주어지고 각 수에 1을 빼거나 1을 더할 수 있습니다. 가능한 경우 1. 현재 수 1 빼기 2. 현재 수 그대로 사용 3. 현재 수 1 더하기 위의 3가지 경우를 모두 DFS로 탐색하였습니다. 그리고 이전의 값과 차가 동일하면 계속 DFS로 탐색합니다. 가능한 경우들이 여러개가 나오는데 최소의 연산을 한 경우를 출력해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter;..
그리디 문제입니다. A와 B로 이루어진 문자열 2개가 주어집니다. 2개의 문자열을 S와 T문자열이라 할때 S문자열을 T문자열로 만들 수 있는지 찾아야합니다. 2가지 경우의 수 1. S문자열의 뒤에 A를 추가한다. 2. S문자열을 뒤집고 뒤에 B를 추가한다. S문자열을 T문자열로 바꾸는 것이 아닌 T문자열을 S문자열로 바꿀 수 있는지 찾는 단계를 밟으면 해결할 수 있습니다. 1번과 2번 결국 뒤에 A와 B를 추가합니다. 이는 S문자열의 마지막 글자를 보면 어떤 작업이 이루어 졌는지 볼 수 있습니다. 마지막 글자가 A면 => A를 추가한 상태 마지막 글자가 B면 => 문자열을 뒤집고 B를 추가한 상태 이를 토대로 마지막 글자가 A면 => A를 빼기 마지막 글자가 B면 => B를 빼고 문자열을 뒤집기 위의 과..
투포인터 문제입니다. 3 가지 경우가 있습니다. 1. 문자의 좌우가 대칭되는경우 회문 (0) 2. 문자의 한글자를 빼서 대칭되는 경우 유사 회문 (1) 3. 둘다 아닌 경우 (2) 왼쪽과 오른쪽에 각각 포인터를 둡니다. 두 위치에서 값이 같은지 확인하고 같으면 한칸씩 안쪽으로 이동합니다. 왼쪽과 오른쪽의 위치가 같아지거나 왼쪽이 더 커진 경우 반복을 멈춥니다. 만약 값이 다른 경우 한글자를 뺄 수 있으므로 2가지 경우가 가능합니다. 1. 왼쪽을 뺀 경우 2. 오른쪽을 뺀 경우 1번의 경우 왼쪽만 한칸 오른쪽으로 이동해서 위의 과정을 반복합니다. 2번의 경우 오른쪽만 한칸 왼쪽으로 이동해서 위의 과정을 반복합니다. 위의 경우 이미 한 글자를 지웠으므로 체크를 해둡니다. 결과적으로 2가지 경우가 발생합니다...
브루트포스 문제입니다. 규칙에 맞게 가능한 경우의 수를 구해야합니다. 규칙 1. 두 문제 이상 2. 문제의 난이도의 합이 L보다 크거나 같고 R보다 작거나 같음 3. 가장 어려운 문제와 가장 쉬운문제의 차이는 X보다 큼 DFS를 돌면서 위의 규칙에 해당하면 카운팅을 해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int n; static int l; static int p; static int x; ..
누적합 문제입니다. 개똥벌레가 직선으로 이동할 때 파괴해야 하는 장애물의 최솟값과 그러한 구간의 개수를 구해야합니다. 장애물은 높이가 주어지고 아래, 위, 아래, 위 ... 아래, 위 순서로 설치됩니다. 먼저 위 아래를 구분해서 배열을 만들어주었습니다. 그리고 각 높이의 개수를 구해줍니다. 그렇다면 예를들어 아래와 같은 배열이 만들어집니다. 위 3미터 2개 위 2미터 3개 위 1미터 1개 아래 3미터 1개 아래 2미터 2개 아래 1미터 2개 위처럼 만들어졌다고 가정하면 누적합을 사용해서 값을 더해줍니다. 3미터인 경우 2미터도 포함이므로 3미터를 2미터에 더해줍니다. 더해진 2미터를 1미터에 더해줍니다. 누적합 배열이 만들어졌습니다. 위 3미터 2개 위 2미터 5개 위 1미터 6개 아래 3미터 1개 아래..