분류 전체보기80 [DP] 10844 - 쉬운 계단 수 (실버 1) with Python https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 주저리 주저리 이런 유형의 문제는 제발 꼭 풀어보자. 언젠간 크게 도움이 되는 것 같다. 문제는 짧지만 어렵게 내거나 처음 풀면 많이 당황 스러울 수 있는 문제인 듯 하다. 중요 표시 문제 해결 이런 케이스는 무조건 표를 만들어서 그려야 한다. 길이/ 끝숫자 0 1 2 3 4 5 6 7 8 9 1 x 1 1 1 1 1 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 3 1 3 3 4 4 4 4 4 3 2 가로가 끝 숫자 세로가 N이라고 해보자 규칙이 보이는가? 자세히 보면 일단 끝 숫자가 0일 때랑 9일 .. 2023. 2. 19. [DP] 1463 - 1로 만들기 (실버3) with Python https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 주저리 주저리 개인적으로 이런 유형의 문제는 DP를 한다면 한번쯤은 풀어보면 좋을 것 같다는 느낌이 든다. 이런 유형의 문제는 어디서든 간단한 문제로 볼 수 있기 때문이라 생각한다. 문제 해결 위 조건들을 이용해 1을 만드는 최소의 횟수를 구하는 문제이다. 아주 간단하다 각 조건에 맞게 dp를 넣으면 된다 예를들어 2는 2로 나누어 떨어지니 dp[2//2] + 1로서 1이 되니 정답이 된다. 여기서 중요한 것은 dp값을 아주 크게 주는 것이다. (최소 값을 구하는 것이니) 이런식으로 문제에 적용 시키면 된다. .. 2023. 2. 19. [DP] 2579 - 계단 오르기 (실버 3) with Python https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 주저리 주저리 이번 문제는 생각보다 조건이 까다로운데 난이도는 낮았다. 솔직하게 말해서 이 문제의 난이도가 다른 실버1이나 골드5정도보다 높다 생각한다 개인적으로 푸는데 어려웠고, 얻어가는것이 많아졌다. 미션 해결 조건을 보자 계단은 한 계단 or 두 계단 건널 수 있다. 연속된 세 계단은 안된다 마지막은 반드시 밟자 => 딱히 무의미 여기서 어려운 점은 1번과 2번이다. 특히 2번을 어떻게 해결해야 하는 것.. 2023. 2. 19. [DP] 1932 - 정수 삼각형 (실버1) with Python https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 주저리 주저리 순간 그래프 모양이여서 dfs로 한 단계씩 내려가는 문제인가 싶었다. 하지만 다시 보니 내려갈 수 있는 방향이 정해져있고, 이전 값을 활용 가능하였다. => dp구나 그럼 한번 풀어보자 문제 해결 간단하게 위에서부터 내려가면서 더하거나 아니면 역으로 밑에서부터 위로 올라간다 이런 두가지 방식 중에서 선택하면 될거 같은데, 일단 나는 위에서부터 내려가기로 했다. 여기서 중요한 점이 있다. 맨 왼쪽과 오른쪽은 위에서 내려오는 값이 고정이다. 그 외의 값들은 .. 2023. 2. 18. 이전 1 ··· 13 14 15 16 17 18 19 20 다음 728x90
