https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 탐색, 그래프 이론, 다이나믹 프로그래밍 설명 DFS를 사용하여, 직전 파이프의 형태 (가로, 세로, 대각선)을 참고하여 풀이할 수 있는 문제입니다. 처음엔 DFS 없이 DP만을 사용하여 풀이하려고 했으나, 생각보다 잘 되지 않아서, 마침내 그래프 탐색 문제인걸 깨닫고 푼 문제였습니다. 소스코드 전체 소스코드 import java.io...

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 난이도 : 실버 3 태그 : 다이나믹 프로그래밍 설명 정수 4를 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 으로 나타내는... 프로그램을 짜고 있었는데 뭔가 이상했습니다. 이 문제, 뭔가 실버3 같지가 않았습니다. 뭔가 쌔한 느낌을 받은 저는, 어... 이거 생각해보니 굳이 1, 2, 3으로 나타낼 필요까진 없네? 라는 것을 뒤늦게야 깨달았고, 아 이거 점화식이구나! 라는 생각이 마침내 떠올랐습니다. 그 즉시 각 항들을 구해보며 규칙성을 찾기 시작했습니다. a[1] = ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 난이도 : 실버 4 태그 : 다이나믹 프로그래밍 설명 동적계획법 (다이나믹 프로그래밍)을 이용해 풀 수 있는 문제입니다. 2로 나누기, 3으로 나누기, 1 빼기 중 하나를 통해 1로 만들 수 있는 최소한의 연한 횟수를 구하는 문제인데, 그리디(탐욕법)으로 생각할 수 있으나, 때로는 무조건 3으로 나누는 것이 더 효과적이지 않을 수 있습니다. 소스코드 import kotlin.math.min fun main() { val n = readLine()!!.toInt() val dp = Array(n + 1) { 0 ..