Java

문제 접근 방식 어떻게 풀어야할지 모르겠어서 일단 각 자리수별로 만들 수 있는 경우들을 직접 나열해보고서 규칙을 찾아보았다. 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010 1000000 1000001 1000010 1000100 1000101 1001000 1001001 1001010 1010000 1010001 1010010 1010100 1010101 각 자리수별로 경우의 수를 세어보면 1, 1, 2, 3, 5, 8, 13, ... 이런식으로 증가하는 것을 알 수 있는데 어디서 많이 본거 같다면 생각하는 그 피보나치 수열이 맞다. 1과 2의 경우..

문제 접근 방식 기존 1로 만들기 문제에 1이 되는 순서까지 출력하는게 추가된 문제기에 기존 DP 테이블 외에도 순서를 기록할 배열을 더 만들어서 기록해주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] dp = new int[n + 1]; int[] history = new int[n + 1]; for (int i = 2; i dp[i/2] + 1) { dp[i] = dp[i/2] ..

문제 접근 방식 Prefix Sum 알고리즘을 사용해 풀 수 있는 문제로 i ~ j까지의 구간합은 (i 까지의 합) - (j-1까지의 합)이라는 공식을 이용해 DP 테이블에는 i까지의 합들을 저장하고 위의 공식대로 계산해주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Inte..

문제 접근 방식 11726번 문제에서 2*2 타일의 경우가 추가된 문제다. i번째에 놓을 수 있는 경우가 기존 문제에서는 DP[i-1] + DP[i-2] 였다면 이번 문제에서는 DP[i-2]를 한 번 더 더해주면 된다. DP[i-2]를 한 번 더 더해주는 이유는 이전 문제 설명글에서 설명한거처럼 1*2 타일을 놓는 경우는 나머지 한층도 1*2 타일을 놓을 수 밖에 없어 사실상 2*2타일을 놓는 경우와 같기 때문에 해당 경우를 한 번 더 계산해 주기만 하면 된다. 따라서 DP 테이블의 초기값은 기존 문제의 테이블에서 2번째 경우에 한 가지를 더 추가해서 DP[1] = 1, DP[2] = 3이 되고 이 테이블을 기준으로 계산해주면 된다. 풀이 public class Main { public static vo..

문제 접근 방식 강의에서 설명해 주기 전까진 DP 문제일 줄은 생각도 못하고 있던 문제다... 일단 위와 같은 타일을 채워야 할 때 가장 위의 칸부터 채우는 경우를 살펴 보면 2*1 타일은 이렇게 하나를 둘 수 있는데 그러면 정확히 2*(n-1) 칸이 남게 된다. 1*2 타일의 경우에는 어차피 한 층에 1*2 타일을 쌓으면 다른 한 층도 무조건 1*2 타일을 쌓을 수밖에 없으니 2*(n-2) 칸이 남게 된다. 결국 이 한 칸에 올 수 있는 경우의 수는 (n-1) + (n-2)에 해당한다. 눈치가 빠른 사람은 이 공식을 어디서 많이 봤다고 생각할 수도 있는데 피보나치수열과 똑같은 공식이다. 이제 문제를 풀 수 있는 식은 구했으니 DP 테이블을 만들어야 하는데 간단하게 i일 때 경우의 수를 저장할 DP [N..

문제 접근 방식 백트래킹이나 다중반복문으로도 풀 수 있는 문제지만 시간제한을 보면 그렇게는 풀 수 없는 문제들이라 DP를 사용해서 풀었다. 1 ~ N번 집까지 있을 때, N번 집을 가장 적은 비용으로 칠할 수 있는 경우는 N-1번째 집을 칠한 경우 중 가장 적은 비용 + 현재 칠할 수 있는 색깔이다. RGB 264083 496057 138999 위와 같이 3개의 집과 각 집을 칠하는 색깔별 비용이 주어졌을 때를 살펴보면 26 -> 60 OR 57 -> 13 OR 99 / 13 OR 89 40 -> 49 OR 57 -> 89 OR 99 / 13 OR 89 83 -> 49 OR 60 -> 89 OR 99 / 13 OR 99 이전 집을 칠한 색깔을 제외한 각각의 색깔들 별로 칠할 수 있다. DP 테이블을 각 ..

문제 접근 방식 길이가 N인 수열에서 같은 숫자끼리는 최대 K번까지만 사용한 부분 수열을 구해야 한다. 각 숫자들마다 등장 횟수를 기록해야하기 때문에 불리언 배열이 아닌 정수형 배열에 특정 숫자가 등장 할 때마다 해당 인덱스에 카운트를 증가시키면서 투 포인터로 탐색을 하다가 특정 숫자가 K번 이미 등장 했을 때 또 등장했다면 만들 수 있는 부분 수열의 끝이므로 현재 부분 수열의 길이를 구한 후에 현재 까지 가장 긴 부분 수열의 길이인지 비교하고 값을 바꿔주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStre..

문제 접근 방식 k개의 초밥을 연속으로 먹었을 때 가장 다양한 종류의 초밥을 먹을 수 있는 경우를 구해야 하는 문제로 초밥을 k개 먹었을 때 중복 되지 않은 초밥이 몇 개인지를 찾으면 된다. 탐색은 이전의 투포인터 문제들과 마찬가지로 배열의 첫 인덱스를 기준으로 k개의 초밥을 먹을 때까지 탐색을 하고, 시작 인덱스를 1 증가시켜주면 된다. // 연속으로 먹은 횟수 // 회전 벨트의 초밥 목록 1234k 7973027925 1234k 7973027925 1234k 7973027925 1234k 7973027925 1234k 7973027925 4k123 7973027925 34k12 7973027925 234k1 7973027925 탐색의 진행 과정은 위와 같다. 불리언 배열을 이용해 이미 등장한 초밥이라..