본문 바로가기

BOJ749

백준 2491 자바 - 수열 (BOJ 2491 JAVA) 문제 : boj2491 1. 연속해서 커지는 경우(같은 것 포함)만 일단 생각해보자. 주어지는 N개의 숫자에 대해서, 숫자가 작아진 경우 카운팅을 1로 되돌려보자. 그럼 다음과 같이 증가(같은 것 포함)하는 경우에 대해 각 구간에서 얼마나 긴 길이를 가지는지 알 수 있다. 2. 그럼 감소하는 경우도 마찬가지다. 값이 이전보다 커지는 경우 카운팅을 1로 되돌리면서 계속 세어나가면 된다. 이 문제의 경우엔 커지거나, 작아지는 수열 중 답을 구해야한다. 하지만 다를건 없다 그냥 하나씩 입력받으면서 증가하는 경우의 카운팅과, 감소하는 경우의 카운팅을 따로따로 해주면 된다. 한번에 세지 못하고 따로따로 세줘야 하는 이유는, 모든 수가 동일한 구간이 포함된 경우 (e.g. '1 1 1 1 1 1')를 제대로 판단하.. 2021. 12. 31.
백준 2225 자바 - 합분해 (BOJ 2225 JAVA) 문제 : boj2225 1. 0부터 N까지에서 '0부터' 부분 때문에 좀 헷갈렸다. '덧셈의 순서가 바뀐 경우는 다른 경우로 센다' 라는 부분 때문에, 예를들어서 N이 1이라 해도 K가 5라면 1+0+0+0+0 / 0+1+0+0+0 / ... / 0+0+0+0+1 이 가능해진다 ㅋㅋㅋ 0의 더하는 순서라니 인지적으로는 좀 이상하긴 하지만, 사실 문제 푸는데는 상관없다! '2'를 보면 알겠지만, 그냥 1부터 N까지라고 해도 점화식이 달라질 뿐이다. 2. K-1개의 수를 합해 만든 어떠한 값이 있다. 이 값에 0부터 N까지의 정수를 더한다면 K-1개의 수로 만든 합에 1개의 정수를 더 더한 것이므로, K개의 수를 사용해 만든 어떠한 합이 될 것이다. 그렇다면 0부터 N까지의 정수를 사용해서, X개의 수를 합.. 2021. 12. 30.
백준 2133 자바 - 타일 채우기 (BOJ 2133 JAVA) 문제 : boj2133 1. 우선, 2x1과 1x2짜리 타일을 사용해야 하므로 무슨짓을 하던 n이 홀수라면 전체 칸 수(3 x n)가 홀수이므로 2칸짜리 타일로 타일링이 불가능하다. 즉, n이 짝수일 때만 타일링이 가능하다. 이 부분은 예외로 처리해준다. 2. 가장 기본적인 규칙성을 찾아보자. n=2일 때 3가지 모양이 나온다. 3. 그럼 n=4일 때는 n=2일 때 나왔던 모양에서 각각의 경우 3가지 모양이 더 추가되므로 'n=2일때의 모양 x 3'이 됨을 쉽게 알 수 있다. 예를 들어 위 n=2일때 중 첫번째 그림에 대해서만 그려보면 다음과 같다. 일단 여기까지, f(n)을 3 x n 타일링에서 n개의 가로칸으로 가능한 타일링의 경우의 수라 하자. 그럼 f(4) = f(2) * 3 임을 알 수 있다. .. 2021. 12. 30.
백준 2193 자바 - 이친수 (BOJ 2193 JAVA) 문제 : boj2193 1. N=1 일 때를 생각해보자. 0으로 시작하면 안되므로, 0으로 끝나는 수는 0개이고 1로 끝나는 수는 1개이다. (0과 1) 2. N=2 일 때를 생각해보자. 0으로 끝나려면 어떻게 해야 할까? 이 문제의 경우 1이 두번 연속으로 나오지 않기만 하면 된다. 따라서 이전 값이 0으로 끝나거나, 1으로 끝나거나 상관 없이 0을 붙일 수 있다. 반면에 끝이 1로 끝나려면 이전에 0으로 끝난 경우에 대해서만 1을 추가로 붙일 수 있다. 3. 이제 위의 규칙을 계산하기 위해 dp를 사용해보자. dp[n][x(=2)]를 n자리수에서 x로 끝나는 경우의 수라 정의하자. 이 때 n=5인 경우에 대해 그려보면 다음과 같다. 점화식으로 나타내면 dp[n][0] = dp[n-1][0] + dp[.. 2021. 12. 30.
백준 2294 자바 - 동전 2 (BOJ 2294 JAVA) 문제 : boj2294 1. 우선 문제에서 필요없는 정보를 제한해보자. 1.1 '사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.' -> 이 조건은 해당 가치를 표현하는 경우의 수를 구할때나 의미가 있다. '사용한 동전의 최소 개수'를 구하는 문제이므로 무시해도 된다. 1.2 '가치가 같은 동전이 여러 번 주어질 수도 있다.' -> 가치가 동일한 동전의 경우 연산을 느리게 할 뿐이므로, 동일한 동전이 주어진 경우는 HashSet 등을 사용해 제거하면 될 것임을 생각할 수 있다. 1.3 'k 2021. 12. 30.
백준 2293 자바 - 동전 1 (BOJ 2293 JAVA) 문제 : boj2293 1. 우선 문제를 좀 더 간단히 변경해서 봐보자. 1,2,5의 가치를 가지는 동전이 있고, 그 가치의 합이 10이 되게 하려 한다. 그리고 문제와 다르게 동전의 구성이 같아도 순서가 다르면 다른 경우로 치고 생각해보자. 그럼 1차원 배열을 활용한 dp로 아래와 같이 풀 수 있다. (냅색 문제처럼 풀면 된다.) 1.1 우선 초기값이다. dp[idx]는 1,2,5의 동전들을 가지고 idx의 가치를 가지는 경우의 수를 나타낸다. dp[0]은 실제론 불가하지만, 초기값으로 넣어준다. 그래야 동전 하나를 가지고 표현할 수 있는 경우에 대해서도 별도로 처리하지 않고 점화식 하나로 계산하기 편하다. (예를들어 2의 가치를 표현하려면 동전2짜리 하나만 쓸 수 있다. 식으로는 dp[2-2]이다. .. 2021. 12. 29.
백준 2757 자바 - 액셀 (BOJ 2757 JAVA) 문제 : boj2757 R값은 그냥 그대로 출력하면 된다. C값의 경우, 10진수를 26진수로 변경한다고 생각하면 좀 편하게 생각할 수 있다. C값은 뒤부터 한 자리씩 26으로 나눠보면서 맞는 문자를 매칭시키는 방식으로 찾을 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder answ.. 2021. 12. 28.
백준 2012 자바 - 등수 매기기 (BOJ 2012 JAVA) 문제 : boj2012 1. 흔히 생각해볼만한게, 예를들어 '1 8 4 5 6'과 같은 입력이 있는 경우 총 1~5등 까지를 매칭시켜야 한다. 그렇다면 1~5등 사이 중 일단 자기가 원한 등수가 가능한 녀석들을 매칭시키자. 그럼 1, 4, 5는 1~5등 내에 매칭이 가능할 것이다. 이제 8과 6이 남는데, 당연하게도 정렬해서 매칭시키는 것이 더 정답에 가까울 것임을 유추할 수 있다. 따라서 정렬 후 차례대로 남는 위치에 매칭시키면 답을 구할 수 있다. '1'의 방법을 정리하면 1.1 N을 입력받는다. 1.2 1~N에 바로 매칭이 가능한 예상등수를 매칭시킨다. 1.3 남는 등수를 정렬한 후, 1~N 사이 남는 등수에 매칭시킨다. 이 된다. 2. 그런데 사실 더 쉬운 방법이 있다. 어차피 (|A-B|)의 합.. 2021. 12. 27.
백준 20127 자바 - Y-수열 (BOJ 20127 JAVA) 문제 : boj20127 증가수열 또는 감소수열인 것은 해결 로직을 세우는데에 상관이 없다. 증가수열, 감소수열 둘다 별도 로직으로 계산한다고 생각하면 그 중 작은걸 출력하면 된다. 기본적으론 이런데, 이 문제의 경우 정답률이 낮은만큼 많은 경우를 세세하게 예외처리해줘야 통과할 수 있다. 이하 여러가지 케이스에 대해 설명해본다. 1. 기본 로직은 증가수열을 체크한다면 수가 작아지는 부분을, 감소수열을 체크한다면 수가 커지는 부분의 개수가 2개 이상이라면 증가 혹은 감소수열이 될 수 없다. 예를들어 '예제 입력 1'에 대해 증가수열로써 체크한다면 감소하는 경우가 1번 이하이므로 가능하다! 하지만 감소수열로써 체크한다면 감소하는 경우가 2번 이상이므로 감소수열로는 만들 수 없다. 2. 이번엔 '1'와 같은 .. 2021. 12. 26.
백준 10997 자바 - 별 찍기 - 22 (BOJ 10997 JAVA) 문제 : boj10997 1. 일단 규칙부터 유추해보자. 대강 n이 주어질 때 우측상단부터 시작해서 n-0.5 바퀴 돌리는 별찍기라 볼 수 있다. 예를들어 3이라면 2.5바퀴를 돌린 형태이다. 2. 좀 더 구체적으로 짤 수 있는 로직을 생각해 보자면, 1일 때는 그냥 예외로써 '*' 하나만 출력해주면 되겠고, n이 2 이상이라면 row의 개수는 3+4*n, column의 개수는 1+4*n 이 된다. 그리고 우측 상단부터 시작해서 좌,하,우,상의 방향을 순서대로 돌리면서 갈 수 있는 곳까지 별을 찍으면 된다. 갈 수 있는 조건은 배열의 끝 혹은 가려는 방향으로 2칸 앞이 이미 별인 경우 해당 위치까지만 찍을 수 있다. 즉 row와 column 개수에 대한 점화식만 잘 세우고, 그 이후로는 단순 구현으로 풀.. 2021. 12. 25.

티스토리툴바