[백준 3004] 체스판 조각

3004번: 체스판 조각

• 나무판을 n번 자를 때 최대 몇 조각 이 되는지 출력하는 문제
• 크게 반복문으로 구하는 방법과 규칙을 찾아 구하는 방법이 있다.
• 시간제한에 걸릴까 봐 규칙을 찾는 방식으로 접근했다.
  • 근데 결국 사용한 게 reduce라서.. 쉽게 반복문으로 접근할걸 싶기도. (시간제한에 걸리진 않는 듯 - n의 최댓값이 100이라)
• 규칙
  • 1 : 2
  • 2 : 4
  • 3 : 6
  • 4 : 9
  • 5 : 12
  • 6 : 16
  • 7 : 20
  • 8 : 25
  • 9 : 30
  • 10 : 36

풀이1 (나의 풀이)

• 1일때 초기값이 2, 나머지는 +2 +2 +3 +3 +4 +4 .. 패턴
• n이 홀수일 때는 초기값 2에, 2부터 (n + 1) / 2 까지 더한 값의 곱하기 2
  • n=7 → 2 + (2…4) * 2 = 20
• n이 짝수일 때는 초기값 2에, 2부터 n / 2 까지 더한 값의 곱하기 2, 그리고 (n / 2) + 1 을 더함
  • n=8 → 2 + (2…4) * 2 + 5 = 25
• 다만 이 방식을 사용할 경우..
  • 범위 연산자 떄문에 n이 1일 때와 2일 때는 직접 처리 필요
  • 반복문을 피하려고 공식을 구해보려 했지만 결국 reduce를 사용했음ㅎㅎ

let cut = Int(readLine()!)!
var answer = 0
if cut == 1 {
    answer = 2
} else if cut == 2 {
    answer = 4
} else {
    if cut % 2 == 1 {
        let cutHalf = (cut + 1) / 2
        answer = 2 + (2...cutHalf).reduce(0, +) * 2
    } else {
        let cutHalf = cut / 2
        answer = 2 + (2...cutHalf).reduce(0, +) * 2 + (cut / 2 + 1)
    }
}
print(answer)

풀이 2 ( 정답코드 중 발췌 )

아래와 같이 정말 공식을 찾아 계산하신 분들도 있었다. 👍

반복문을 쓰지 않으므로 시간복잡도면에서 유리하다.

var x = Int(readLine()!)!
print(((x/2)+1)*(x-(x/2)+1))

let input = Int(readLine()!)!
if input % 2 == 0 {
    let a = input / 2 + 1
    print(a * a)
} else {
    let a = (input + 1) / 2 + 1
    print(a * a - a)
}