백준
-
[백준 9655번] 돌 게임 Java 풀이문제풀이/백준 2021. 9. 15. 23:02
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 DP로 문제를 풀어도 되며 게임을 생각해 보면 DP가 아닌 그냥 간단하게 문제가 풀립니다. 문제 풀이 전 문제에 대한 이해가 필요한 부분이 있습니다. 문제에서 말한 완벽하게 게임을 했을 때는 본이이 이기기 위한 경우를 말하는 것 입니다. 즉 돌이 3개 이상 남은 경우 3개를 가져가는 것을 말하는 것입니다. ● 간단한 문제 풀이 게임에서 돌을 가지고 갈 수 있는 수는 1개와 3개로 모두 홀수개입니다. 즉 3개를 들고 가는 것과 1개를 3번 들고 가는 것이 같은 결과를 만드는 것입니다. 돌이 3개가 있을 때..
-
[백준 19947번] 투자의 귀재 배주형 Java 풀이문제풀이/백준 2021. 9. 14. 23:09
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 DP를 이용하여 풀어보았습니다. 이자는 투자기간이 끝나는 시점에 얻을 수 있다고 하였습니다. 또한 투자 방식은 매년 변경이 가능합니다. 여기서 투자 방식은 매년 변경이 되지만 투자기간이 끝나는 시점에 이자를 얻을 수 있으므로 한번 투자한 투자유형을 변경하는 것은 곧 이자를 0원 얻는 것이므로 투자 유형을 변경하는 것은 최고의 이자를 받을 수 있는 방법이 아닙니다. 만약 입력으로 투자 기간이 0이 주어진다면 가장 많은 이득을 본 금액은 투자를 시작하고자 한 금액이 될 것입니다. 그 말은 DP[0]의 값은 ..
-
[백준 1463번] 1로 만들기 Java 풀이문제풀이/백준 2021. 9. 13. 00:06
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 먼저 입력으로 주어진 N 값을 1로 만드는 데 필요한 최소한의 연산 횟수를 구하기 위해 1부터 N-1까지의 수를 1로 만드는 최소한의 연산 횟수가 필요하였습니다. 1은 1로 만드는 데 필요한 최소한의 연산 횟수는 0입니다. 2는 1로 만드는 데 필요한 최소한의 연산 횟수는 1입니다. (※2를 2로 나누면 1이 됨) 3은 1로 만드는 데 필요한 최소한의 연산 횟수는 1입니다. (※3을 3으로 나누면 1이 됨) 자 그럼 4의 경우는 어떠할까요? 4는 2로 나누어떨어지는 수입니다. 4를 2로 나누면 2가 되며 1번의 연산..
-
[백준 2872번] 우리집엔 도서관이 있어 Java 풀이문제풀이/백준 2021. 9. 9. 12:44
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 먼저 입력으로 알 수 있는 항목은 총책의 수와 현재 책이 쌓여 있는 형태를 알 수 있습니다. 3 1 4 5 2 배열의 왼쪽이 위쪽이고 오른쪽이 바닥 쪽이고 위 표처럼 책이 쌓여 있다면 이동이 필요한 책은 1번과 2번입니다. 5번의 경우 입력으로 주어진 책 중 가장 큰 값을 가진 책이므로 어느 위치에 있든 움직일 필요가 없습니다. 4번의 경우는 5번 다음으로 위쪽에 위치하므로 4번 또한 이동이 필요 없습니다. 그럼 3번의 경우는 바로 위쪽이 아니지만, 이동이 필요없는 이유는 무엇일까요? 그건 1번이 움직이면 자연적으로..
-
[백준 11051번] 이항 계수 2 Java 풀이문제풀이/백준 2021. 9. 7. 13:02
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이항 계수는 이항 계수의 수를 나열한 삼각형 모양의 파스칼 삼각형이 있습니다. 이 파스칼 삼각형을 이용하여 문제를 풀 수 있습니다. 먼저 파스칼 삼각형을 배열을 통해 쉽게 이용할 수 있게 그림을 변경해 보도록 하겠습니다. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 세로 열 Index를 변수 N으로 가로 행 Index를 변수 K라고 한다면 유추가능한 점화식으로는 dp[N][K] = dp[N-1][K-1] + dp[N-1][K]라는 점화식이 도출된다. 단 N의 값이 0이면 dp[N][..