Java

    [백준,BOJ 10825] 국영수( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 10825] 국영수( JAVA 구현)

    -내 생각 일단 문제 자체의 이해는 쉽고, 무엇을 사용해야 할지 알 수 있었다. 일반적으로 정렬 문제의 경우 특별한 경우가 아니면 Comparator클래스에서 compare 메서드를 오버 라이딩해서 풀거나 클래스로 만들어 Comparable클래스로 compareTo메서드를 오버 라이딩해서 풀어야 하는데, 한 동안 DFS, BFS, DP 문제만 풀다 보니까 리턴 값이 헷갈려서 약간 막힌 부분이 있었다. -해법 String의 compareTo와 Integer.compare은 왼쪽에 오는 것이 더 작으면 -1(0)을 반환한다. 같으면 0을 반환한다. Comparator의 compare메소드의 경우 두 인자 중, 첫 번째 인자가 다음에 오는 요소(a), 두 번째 인자가 기준이 되는 요소(b)라 할 때, a와 b..

    [백준,BOJ 11052] 카드 구매하기( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 11052] 카드 구매하기( JAVA 구현)

    -내 생각 이 문제의 경우 문제 지문이 상당히 길기 때문에 자칫 어렵게 보일 수 있는데, 그렇게 어려운 문제는 아니라고 생각한다. 문제의 요점을 잘 읽어보면 카드의 개수와 1 ~ n개의 카드팩으로 이루어진 가격 p1 ~ pn이 주어질 때 카드 개수를 살 수 있는 최댓값을 구하는 것이 문제의 요지이다. 즉, 예제 입력 1의 경우 4개의 카드를 사고자 할 때, 카드 1개로 이루어진 p1의 가격, 카드 2개로 이루어진 p2의 가격, 3개로 이루어진 p3의 가격 4개로 이루어진 p4의 가격이 주어지고, 어떤 카드팩을 골라야 최대 비용으로 구매할 수 있는지 묻는 것이다. 처음 접근은 역시 dp테이블을 만든 후 각 경우의 수를 따져보는 것이었다. 즉 카드를 4장 구매하고 싶다고 할 때, 각 가격별로 카드를 1장 살..

    [백준,BOJ 2011] 암호코드( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 2011] 암호코드( JAVA 구현)

    -내 생각 처음 문제를 풀 때, dp테이블을 그려보려 했는데 감이 잡히질 않았고, 어떻게 풀어야 할지 감이 잡히지 않아 여러 방법으로 시도해보았는데 풀리지 않았다. 특정 예시를 들어서 테이블을 그려야 했었는데, 처음에 그릴 때, 입력값인 암호가 1일 경우 A, 2일 경우 B,... 11일 경우 AA, K.. 같은 방식으로 생각해서 접근이 불가능했었다. -해법 이 문제의 경우 푸는 방식이 다른 DP들과 별로 다르지 않았다. 우선 입력 예제 25114로 예시를 들면, DP에서 많이 썼던, 각 글자를 마지막 숫자로 보는 방식이다. 즉 2부터 2가 마지막으로 오는 경우의 수를 구하고, 다음 5가 마지막으로 오는 경우의 수를 구하고 와 같은 방식이다. 그러나 이 문제에서는 주의해야 할 점이, 1부터 26까지의 숫..

    [백준,BOJ 2225] 합분해( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 2225] 합분해( JAVA 구현)

    -내 생각 처음 문제를 접했을 때는 어떻게 접근해야 할지 감이 잡히지 않았다. 그러나 조금 생각해 봤더니 어느 정도 길이 보였다. 처음 접근한 방법은 각 경우의 수를 따져보는 것이었는데, 이 문제의 경우는 자리 수가 고정되어 있는 것이 아닌, 입력값에 따라 자릿수가 달라지기 때문에 각 자릿수에 따라 경우의 수를 따져야 될 것 같았다. 예를들어 예제 입력의 경우 자리 수가 2자리 이기 때문에, 자리 수가 1인 경우를 따진 후 자리 수가 한 자리 늘어났을 때 이전 자리 수의 경우의 수를 활용하는 방식으로 표를 완성할 수 있었다. -해법 위의 방식으로 접근해보아야겠다는 생각을 한 후 경우를 따져 보았다. 우선 n이 4이고 k가 3일 때를 아래의 표를 보면서 따져보자. 첫 번째로 자리 수가 한 개일 경우는 n보..

    [백준,BOJ 2133] 타일 채우기( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 2133] 타일 채우기( JAVA 구현)

    -내 생각 및 해법 이 문제 역시 타일 채우기 문제로, 예전에 유튜브 강의를 통해 접해 봤던 문제였다. 각 n의 경우에 따라서 타일의 모양을 그려보면 2x1, 1x2크기의 타일밖에 존재하지 않기 때문에 3xN크기의 타일을 채울 때, n이 1, 3, 5... 등 홀수의 경우에는 채울 수 없다는 것을 알 수 있다. 또한 n이 2일 때는 3개, 4일 때는 2의 경우의 수에서 새로운 모양 2가지가 등장해 총 11가지의 수가 등장한다. 이러한 새로운 모양은 n이 짝수로 증가할 때마다 2가지씩 새로운 모양이 등장하기 때문에 점화식을 세워보면, dp [n] = dp [n-2] * 3 + dp [n-4] *2 + dp [n-6] * 2.... 식으로 증가하게 된다. 이 때 주의하지 못했던 점이 있는데 바로 n이 0일 ..

    [백준,BOJ 1699] 제곱수의 합( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 1699] 제곱수의 합( JAVA 구현)

    -내 생각 이 문제의 경우 처음에 접근을 1, 2, 3 더하기 문제처럼 접근을 해버려서 오답 처리를 받은 문제였다. 즉, n이 1일 때, 1의 제곱으로 1개, 2일 때 1의 제곱으로 2개, 3일 때 1의 제곱으로 3개... 식으로 증가한다는 규칙을 찾아서 이전 dp배열에서 1개씩 증가하는 식으로 풀었다. 그러나 문제에서도 언급되어 있듯이, 최소항의 개수를 구하기 위해서는 n보다 작은 제곱수부터 구해나가야 최소항을 구할 수 있는 것이다. 해당 규칙을 알고도 다시 시도해서 풀었는데 정답을 받긴 했지만. 아슬아슬하게 통과한 수준이라 다른 분들의 블로그를 참고해야 했다. -해법 내가 푼 방식은 제곱수와 n이 일치하면 1을 저장하는 방식으로 진행했는데, 그렇게 할 필요가 없이, n값에서 특정 수의 제곱을 빼주면 ..

    [백준,BOJ 11055] 가장 큰 증가 부분 수열( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 11055] 가장 큰 증가 부분 수열( JAVA 구현)

    -내 생각 이 문제는 이전에 풀었던 가장 긴 증가 부분 수열인 LIS 문제와 동일한 문제였다. 차이점이라 한다면, DP 배열에 저장되는 값이 부분 수열의 길이가 아닌, 부분 수열의 합이 된다는 점이다. 그렇기 때문에 기본이 되는 알고리즘은 LIS를 구하는 문제와 동일하다. -해법 이런 식의 부분 증가수열은 기준점을 잡은 후 기준점 이전까지의 수들과 비교하여 자신이 큰 경우만 DP 배열을 갱신해주면 된다. 예를들어 2를 기준으로 잡았을 때, 2의 이전 숫자들인 과 100을 2와 비교해서 2가 큰 경우, 비교했던 숫자가 가지고 있는 dp값 + 기준이 되는 자신의 값으로 갱신해주면 되는데, 이때 주의해야 할 점은 100은 2보다 크기 때문에 자신의 dp배열을 갱신해주어야 한다. 이 경우에는 이전에 선택한 값이..

    [백준,BOJ 9465] 스티커( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 9465] 스티커( JAVA 구현)

    -내 생각 이 문제 역시 내 힘으로 풀 수는 없었다.. 처음 생각했던 것은 각 스티커를 붙였을 때와 붙이지 않았을 때를 고려해 각각의 경우의 수에 따라 최댓값을 찾으려 했었는데, 해결하지 못해서 다른 분들의 글을 확인해 보니 고려하지 않은 부분이 있었다. 아직 한참 모자란 것 같다. -해법 우선 하나의 스티커를 기준으로 가능한 경우의 수를 보자. 스티커를 하나 선택하면 해당 스티커를 기준으로 상하좌우는 선택할 수 없다는 제한이 있다. 그렇다면 스티커를 하나 선택했을 때, 가능한 경우의 수는 대각선으로 가는 경우가 존재하는데, 이를 그림으로 표현해보면, 위와 같은 경로가 가능하다. 왜 10이나 60은 갈 수없냐고 할 수 있는데, 10 또는 60, 100으로 바로 갈 경우는 문제의 조건에 부합하지 않기 때문..

    [백준,BOJ 2193] 이친수( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 2193] 이친수( JAVA 구현)

    -내 생각 우선 이런 류의 문제는 쉬운 계단 수는 오르막 수와 같은 방식으로 풀어야 한다는 느낌은 알 것 같다. 그래서 이번 문제의 경우는 dp배열의 설계는 제대로 되었고, 거기서 규칙을 찾는 것 또한 잘 찾았다. 그러나 오답 처리를 받아 어디가 문제일까 고민해보다가 n의 최댓값인 90을 넣어보니 역시 int형 데이터의 범위를 벗어나 제대로 된 답이 나오지 않았다. 항상 테스트 케이스의 범위 중 최댓값을 넣어보는 습관을 들여야 할 것 같다. -해법 해법은 간단하다. 쉬운 계단 수나 오르막 수 처럼 0과 1을 끝자리 기준으로 두고 표를 그려보면 된다. 우선 N이 1일 경우 초기화를 시켜주어야 하는데, 끝 자리가 0일 경우는 올 수 없다. 왜냐하면 0으로 시작하는 경우는 존재하지 않는다고 문제에서 언급했기 ..

    [백준,BOJ 11057] 오르막 수( JAVA 구현)
    코테/백준 온라인 저지(BOJ)

    [백준,BOJ 11057] 오르막 수( JAVA 구현)

    -내 생각 이 문제의 경우 쉬운 계단 수 문제와 아주 유사하다고 생각했다. 문제를 푸는 과정에서도 유사한 것을 알고 해당 해답을 생각해봤는데, 떠오르지가 않아서 어쩔 수 없이 다시 규칙을 찾아보았다. n이 1일 경우 0~9까지의 10개, n이 2일 경우 0~9까지에 n이 1일 경우에서 1씩 감소하는 형태를 띤다는 것은 쉽게 찾아냈다. 그러나 이를 어떻게 dp배열에 표현해야 할지 감이 잡히지 않아서 결국 다른 분들의 블로그를 참고했다. -해법 위와 같은 방식은 맞으나 각 자릿수에서 해당 숫자들을 수의 첫 번째 자리가 아닌, 마지막 자리로 생각하면서 dp 배열을 dp[n][10]으로 구현하여 각 자릿수마다 끝자리의 숫자의 경우 앞에 올 수 있는 숫자의 경우의 수를 저장하면 된다. 예를 들어 아래의 표는 n이..

티스토리툴바