반응형 DP8 [백준 9655] 돌 게임 돌 게임(9655)문제 출처 : https://www.acmicpc.net/problem/9655 돌 게임은 다양한 방식으로 출제되고 있는 유명한 문제 입니다. 다양한 돌 게임중 가장 쉬운 형태의 문제 입니다.우리는 돌을 1개 혹은 3개를 가져갈 수 있습니다. 2개를 가져갈 수 있는 것이 아니라는 점을 기억해야 합니다. 이 때 두 사람은 최선을 다해 게임이 임합니다. 즉 자신이 지는 방향으로는 가지 않는다는 뜻입니다.문제 이해하기N개의 돌이 남았을 때 현재 상근이가 게임을 진행하면 누가 이길지를 출력하는 것이 우리가 만들 함수 입니다. 상근이의 차례에 돌이 1개 혹은 3개 남아있다면 무조건 상근이가 이깁니다. 반대로 2개 혹은 4개가 남아 있다면 무조건 창영이가 이기게 됩니다. 그럼 아래와 같은 함수를 .. 2024. 11. 14. [백준 2193] 이친수 이친수(2193)문제 출처 : https://www.acmicpc.net/problem/2193 0과 1로 이루어진 이진수 중 특별한 성질을 가지고 있는 이친수를 찾는 문제 입니다. 이친수의 성질은 다음과 같이 두 가지 입니다.이친수는 1로 시작합니다.이친수는 1이 연속해서 나타나지 않습니다.이 두 가지 성질을 만족하는 이친수의 개수를 찾는 것 입니다.문제를 보면 DP의 Top-Down으로 문제를 해결할 수 있을것 같습니다. 함수를 만들고 그 함수의 특징을 다음과 같이 정의 하였습니다.solve(n, c)n은 이친수의 길이 입니다. 그리고 c는 마지막 숫자를 나타냅니다. 즉 0 아니면 1이 됩니다. 그리고 이 함수의 리턴값은 길이가 n까지이고 마지막 숫자가 c인 이친수의 경우의 수 입니다.코드 작성하기그.. 2024. 11. 10. [백준 11057] 오르막 수 문제 출처 : https://www.acmicpc.net/problem/11057 간단한 DP 문제 입니다. 점화식이 바로 떠오른다면 문제 없지만 보통 점화식을 바로 떠올릴 수 없습니다. 그런 경우 Top-Down으로 먼저 문제를 해결하고 이를 Bottom-Up으로 바꾸는 것이 좋습니다.아직 Top-Down, Bottom-Up이 무엇인지 잘 모르겠다면 아래 링크를 통해 확인해 보시기 바랍니다.https://wikidocs.net/206429 09. 동적 계획법(다이나믹 프로그래밍)동적 계획법이라 불리는 DP(dynamic programming) 는 큰 문제를 작은 문제로 쪼개어 나가면서 문제를 해결하는 기법 입니다. DP에는 크게 두 가지 방법이 많이 사…wikidocs.net 문제 이해하기Top-Dow.. 2024. 11. 8. [백준 2624] 동전 바꿔주기 문제 출처 : https://www.acmicpc.net/problem/2624 이 문제는 2002년 정보 올림피아드 중등부 2번 문제 입니다. 다빈치코딩 알고리즘 책에서 동전 문제들은 많이 다루었습니다.[백준 2091] 동전 : https://wikidocs.net/265710 06. 동전 [백준 2091][TOC] # 동전(2091) 문제 출처 : [동전](https://www.acmicpc.net/problem/2091) 지금까지 동전0, 동전2, 동전1 순으로 동전 문제를 …wikidocs.net문제 이해하기동전 문제들을 통해서 다양한 문제풀이 방법을 배웠습니다. 동전1(2293) 문제에서 경우의 수를 구하는 방법을 배웠고, 동전(2091) 문제에서 동전의 개수가 정해져 있는 문제를 풀어보았습니다.. 2024. 11. 7. [백준 1328] 고층 빌딩 문제 출처 : https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 문제 이해하기 빌딩을 왼쪽에서 보았을 때, 오른쪽에서 보았을 때를 가지고 빌딩의 순서를 출력하는 문제 입니다. 어려운 문제이지만 차근차근 생각하면 해결할 수 있습니다. 이 문제를 풀 때에는 모든 빌딩이 바닥에서부터 쏟아오른다고 생각하면 좀 더 쉽습니다. 문제의 예로 나온 N = 5, L = 3, R = 2를 생각해 보겠습니다. 총 5개의 건물이 있고 왼쪽에서는 3개의 빌딩이 보이고,.. 2024. 4. 1. [백준 17613] 2019 정올 1차 고등부 "점프" 문제 출처 : https://www.acmicpc.net/problem/17613 17613번: 점프 T개의 줄에 각각 하나의 정수를 출력한다. 각 줄에 출력되는 정수는 구간 [x, y]안의 수들의 점프넘버들 중 최댓값이다. 각 정수는 입력으로 주어지는 구간의 순서에 맞게 출력되어야 한다. 즉, 첫 www.acmicpc.net 이 문제는 2019년 정보올림피아드 1차 고등부 2번 문제 입니다. 점프를 하면서 해당 위치에 갈 수 있는 가장 짧은 점프 횟수를 찾는 문제 입니다. 여기 까지는 쉽지만 범위 안에 있는 모든 짧은 점프 횟수를 찾아 그중 가장 큰 수를 출력해야 합니다. 문제 이해하기 예제 입력에 있는 3번째 경우를 보겠습니다. 12부터 16사이에 가장 큰 점프 횟수를 찾아야 합니다. 먼저 12에 도.. 2024. 2. 29. [백준 17610] 2019 정올 1차 중등부 "양팔저울" 문제 출처 : https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 이 문제는 2019년 정보 올림피아드 1차 중등부 1번 문제 입니다. 양팔 저울을 가지고 만들 수 있는 모든 무게를 찾아 불가능한 경우의 수를 출력하는 문제 입니다. 따라서 1부터 모든 추의 무게를 따져가며 만들 수 있는지, 없는지 확인해야 합니다. 이런 문제는 DP를 통해 풀 수 있습니다. DP의 배낭 문제를 통해 이 문제의 해결 방안을 생각해 볼 수 있습니다. 경우의 수를 따져.. 2024. 2. 23. [백준 10844] 쉬운 계단 수 문제 출처 : 쉬운 계단 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 숫자가 계단수인지 아닌지 확인하며 개수를 센다면 시간초과가 발생할 수밖에 없습니다. 이런 문제를 만나면 직접 경우의 수를 따져보며 문제를 어떻게 풀어야 할지 고민하는게 좋습니다. 예제 입력 확인해보기 예제 입력을 보면 1을 입력 하였을 때 9가 출력 됩니다. 0으로 시작하는 수는 계단수가 아니기 때문에 1부터 9까지의 숫자 아무거나 계단수가 됩니다. 따라서 9가 되는 것입니다. 다음으로 2를 입력하면 17이 됩니다. 왜 17이 되는지 따라가보면 앞서 1을 입력한 숫자들이 계단수가 되기 위해 어떻게 바뀌는지 생각하면 알 수 있습니다. 1은 10이나 1.. 2024. 1. 22. 이전 1 다음 반응형
