반응형
백준 BOJ 3004 - 체스판 조각 / stride 함수
안녕하세요. 개발 중인 정주입니다.
오늘은 백준 BOJ의 3004번 체스판 조각을 풀었습니다.
원래는 수학 문제인제 DP 방식으로 풀어보았습니다.
거기서 거기지만 수학으로 푼 코드도 있습니다.
Github
https://github.com/jeongju9216/swiftAlgorithm
문제 링크
https://www.acmicpc.net/problem/3004
풀이
자른 횟수 | index | dp 값 |
0번 | 0 | 0 |
1번 | 1 | 2 |
2번 | 2 | 4 |
3번 | 3 | 6 |
4번 | 4 | 9 |
5번 | 5 | 12 |
DP 공식
dp[index-1] + (index/2 + 1)
수학 공식
(n/2 + 1) * (n - (n/2 + 1))
최종 코드
let input = Int(readLine()!)!
var dp = [0, 2]
for i in 2 ... input + 1 {
dp.append(dp[i-1] + (i/2 + 1))
}
print(dp[input])
자른 횟수가 0번과 1번인 경우는 미리 배열에 넣었습니다.
input은 1 이상의 값이지만 편의를 위해 0번인 케이스도 넣었습니다.
수학 코드는 저 공식 그대로 작성을 하면 되기에 생략하도록 하겠습니다.
마무리 인사
수학으로 풀면 쉬울 문제를 괜히 DP로 접근했다가 고생했네요.
아니면 옛날의 DP 기억이 새록새록이라 추억이 작용한 것일까요?
감사합니다!
아직은 초보 개발자입니다.
더 효율적인 코드 훈수 환영합니다!
공감과 댓글 부탁드립니다.
반응형