[Swift 알고리즘] 백준 BOJ 3004 - 체스판 조각 / 수학, DP

백준 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 기억이 새록새록이라 추억이 작용한 것일까요?

 

감사합니다!

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.