BOJ

[다이나믹 프로그래밍] ★ 1562번 - 계단 수

2022.05.10

[백준] 1562번 - 계단 수 (한줄평) 간단하다고 생각했지만 0부터 9까지 숫자가 모두 등장했는지 확인하기 위한 아이디어를 떠올리기 어려웠던 문제였다. 비트 마스킹을 이용한 DP 문제 유사 문제: 10844 https://hseungyeon.tistory.com/302 [다이나믹 프로그래밍] 10844번 - 쉬운 계단 수 [백준] 10844번 - 쉬운 계단 수 (한줄평) 생각보다 빨리 아이디어가 떠올라 쉽게 풀 수 있었던 문제! 2차원으로 접근해야한다는 것을 깨달으면 쉽게 풀 수 있다. 한번쯤 복습해보면 좋을 것 같은 hseungyeon.tistory.com 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다. 0으로 시작하는 수는 계단수가 아니다. 수의 길이 n이 주어질 때 0~9까지 숫자가 모..

[Python]알고리즘/백준

[다이나믹 프로그래밍] ▲ 2293번 - 동전 1

2022.05.10

[백준] 2293번 - 동전 1 (한줄평) 오랜만에 풀었더니 dp 문제 감을 잃었다고 느꼈다. 한 끝차이로 계속 틀린 이유을 찾지 못했던 문제.. 다음에 다시 풀어봐야할 것 같다 풀이 시간: 60분 이내 n가지 종류의 동전을 사용해서 가치의 합이 k원이 되는 경우의 수를 구하는 문제다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. (풀이1) 틀린 풀이 1) 문제 해결 아이디어 점화식을 세우기까지는 오랜시간이 걸리지 않았으나 그걸 코드로 구현하는 과정에서 잘못 생각한 부분이 있어서 어려움을 겪었다. 2) 소스코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) # 동전 종류, 가치의합 graph = [int(..

[다이나믹 프로그래밍] ★ 1562번 - 계단 수

[다이나믹 프로그래밍] ▲ 2293번 - 동전 1

티스토리툴바