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

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

→2019.12.01

코테/백준 온라인 저지(BOJ)

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

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

→2019.12.01

코테/백준 온라인 저지(BOJ)

[백준,BOJ 9095] 1, 2, 3 더하기( JAVA 구현)

-해법 dp문제는 풀어도 풀어도 풀이를 봐도 이해가 안 간다.. ㅋㅋㅋㅋ 재능이 없는 건가 이 문제의 경우 1, 2, 3이 고정적으로 이용된다. 그렇기 때문에 우선 1, 2, 3을 만들 수 있는 경우의 수를 만들어야 한다고 한다. 1 ={1}로 한 개, 2 = {1+1, 2}로 2개, 3 = {1+1+1, 1+2, 2+1, 3}으로 4개이다. 그렇다면 4는 어떻게 만들 수 있을까? 고정된 수 세 개를 이용해 우선 4를 만들어 보려 한다면 4= 1+3 / 2+2 / 3+1이 된다. 즉 1, 2, 3의 각 경우의 수에 +1, +2, +3을 해주기만 하면 4를 만들 수가 있는 것이다. 각 경우의 수에 1, 2, 3만을 더해주므로 전체적인 경우의 수는 변합이 없게 되고 결과적으로 4 + 2 + 1로 7개라는 경..

→2019.11.30

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1793] 타일링( JAVA 구현)

-내 생각 우선 타일링 문제를 비롯하여 dp문제들은 기본적으로 점화식 세우는 것이 굉장히 어렵게 느껴진다... 다른 분들의 글을 보면 대다수가 점화식만 써놓은 경우가 많아 왜 저런 점화식이 세워졌는지 알 수 가없다.. 검색을 통해 알아보아도 점화식을 세우는 것은 그저 문제를 많이 풀어보는 수밖에 없다고 한다. ㅠㅠ -해법 당연히 이 문제를 풀지 못해서 다른 분들의 글에서 도움을 얻었다. 문제 자체만으로도 점화식을 세우기 어려웠는데 예제 출력을 보면 알겠지만 웬 난생 처음보는 큰 숫자가 있다.. 우선 점화식을 세워야 하는데, 이 문제의 경우 점화식을 세울 때 오른쪽이 막혔다고 생각하고 (오른쪽이 막힌 경우는 가로의 길이가 n인 경우이다.) n을 1씩 감소 시키면서 생각한다는 것이다. 즉, 가로가 n-1일 ..

→2019.11.30

코테/백준 온라인 저지(BOJ)

[백준,BOJ 11726] 2xn 타일링( JAVA 구현)

-내 생각 우선 DP에 대해서 개념이 없을 때 강의를 보면서 잠깐 풀어봤던 문제로, 다시 풀어 보았다. -해법 DP문제의 경우 점화식을 구하기 위한 경우의 수를 잘 계산해야 하는 것 같다. N이 1일 경우 2X1크기의 타일 1개를 배치할 수 있고, 2일 경우 2X1크기의 타일 2개, 1X2크기의 타일 2개로 총 2개의 경우의 수가 존재하게 된다. N이 3일 경우는 N이 1일 경우와 2일 경우의 타일 배치를 이용하기 때문에 새로운 모양이 등장하지 않는다. 그렇기 때문에 1일 때의 경우의 수 + 2일 때의 경우의 수를 하면 N이 3일 때의 경우의 수가 도출된다. 점화식으로는 dp [i] = dp [i-1] + dp [i-2]로 표현할 수가 있다. import java.util.*; public class M..

→2019.11.30

코테/백준 온라인 저지(BOJ)

[백준,BOJ 10992] 별 찍기-17( JAVA 구현)

-내 생각 이번 문제는 별 찍기-16 문제와 아주 유사한 문제였다. 예제 출력에서 규칙성을 찾아보면, 먼저 마지막 줄은 항상 모든 별을 출력하고, 마지막 행 이전의 행들은 찍었다 안 찍었다를 반복하는 것이 아닌, 특정 범위의 양 끝 부분만 별을 찍는 것이다. 예제 출력 4를 보면, 별 찍기-16과 마찬가지로 n번 째 열에 별을 한 개 찍고 행이 증가할 수록 n을 기준으로 양방향으로 +j씩 별의 범위가 증가하게 된다. 그렇다면 이 범위에서 양 끝에 속하는 열에만 별을 찍어주면 된다. for(int i=0;i

→2019.11.30

코테/백준 온라인 저지(BOJ)

[백준,BOJ 10991] 별 찍기-16( JAVA 구현)

-내 생각 일반적인 별 찍기 문제와는 다른 문제였다. 우선 처음 봤을 때, 주어진 n에 따라 행의 개수가 정해진다는 사실은 알 수 있었는데, 열의 개수를 알 수가 없어서 알아내는 과정이 필요했다. 우선 n이 1인 경우는 1개만 출력하는 것을 정해놓고, 2일 때 열의 개수가 3개, 3일 때 열의 개수가 5개, 4일 때 열의 개수가 7개.... 식으로 간다는 것을 보면, 열의 개수 변화는 1 -> 3 -> 5 -> 7...로 변화하는데, 단순히 2개씩 증가한다는 것을 알 수도 있지만 n의 값에 따라 열의 개수가 정해져야 하므로 n과 함께 고려해보면 2*n -1개의 열이 생성되는 것이다. 이제 열의 개수를 알았으니 규칙을 찾아야 하는데, 예제 출력을 노트에 그려보면, 각 n번 째 자리에 하나를 찍고 출발을 하..

→2019.11.30

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2446] 별 찍기-9( JAVA 구현)

-해법 별 찍기 문제-9이다. 솔직히 별 찍기 문제는 무언가 특별한 기술이 필요한 것이 아니라, 예제 출력의 모양을 본 후 규칙성을 찾아 구현해야 하는 것 같다. 이번 문제의 경우에는 눈에 딱 봐도 앞 뒤로 한 개씩 빈칸이 증가하는 것을 알 수 있다. 1번째 줄에서 앞 뒤로 0개의 빈칸, 2번째 줄에서 앞 뒤로 1개의 빈칸.... 식으로 가는 규칙성을 찾았으면 이제 이를 토대로 구현해보면 된다. 필자는 보통 중앙을 포함해 윗부분을 구현하고 아랫부분을 별도로 구현한다. //윗부분 구현 for(int i=0;i

→2019.11.30

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2522] 별 찍기-12 (JAVA 구현)

-해법 앞선 문제였던 별 찍기-8 문제와 동일한 풀이로 해결할 수 있다. 윗부분에 중간까지 포함해 출력하고, 아랫부분은 별도로 출력하는 것이다. //윗 부분 반복 for(int i=1;i

→2019.11.29

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2445] 별 찍기-8(JAVA 구현)

-해법 이번 별 찍기에서의 규칙성은 1번째 줄은 첫 번째 열과 마지막 열에 1개, 두 번째 줄은 2개,.... 이런 식으로 가게 된다. 필자의 경우에는 윗부분과 아랫부분으로 나누어서 생각하였고, 윗부분에 중앙 부분까지 포함이 되어있다. // 윗 부분 반복문 for(int i=0;i

→2019.11.29

티스토리툴바