[백준 1834] 나머지와 몫이 같은 수

1834번: 나머지와 몫이 같은 수

N이 입력되었을 때, 나머지와 몫이 같은 수를 모두 구하는 문제.

• 3이 입력되면
  • 1 / 3 : 몫 0, 나머지 1
  • 2 / 3 : 몫 0, 나머지 2
  • 3 / 3 : 몫 1, 나머지 0
  • 4 / 3 : 몫 1, 나머지 1 (✔️)
  • 5 / 3 : 몫 1, 나머지 2
  • 6 / 3 : 몫 2, 나머지 0
  • 7 / 3 : 몫 2, 나머지 1
  • 8 / 3 : 몫 2, 나머지 2 (✔️)
  • 9 / 3 : 몫 3, 나머지 1
  • 나머지와 몫이 같은 수는 4, 8 이며, 답은 이 수들을 합한 12이다.
• 🤔 대상 자연수에 제한도 없는데 답이 나올때까지 무조건 나눠야 하나?
  • 아니다. 위 예제의 패턴을 보면 “나머지는 항상 0 부터 N-1까지"의 값을 가진다.
  • 또, 나머지 == 몫 이어야 하는데 나머지의 최댓값이 N-1이기 때문에, 몫 == N 이 되는 시점부터는 구할 필요가 없어진다 (그 이후부터는 몫만 점점 커져 나머지==몫이 될 수가 없으므로).
• 여기까지 결론을 내고 풀어 보았다 ( 풀이1 )

풀이 1

// 시간초과
let n = Int(readLine()!)!
var number = 1
var answers: [Int] = []
while true {
    let 나머지 = number % n // 나머지는 0 ~ n-1
    let 몫 = number / n // 몫은 계속 커지기만 함
    if 나머지 == 몫 {
        answers.append(number)
    }
    number += 1
    if 몫 == n { // 몫이 n과 같아지면 그 이후는 볼 필요 X
        break
    }
}
print(answers.reduce(0) { $0 + $1 })

• 시간초과가 떴다.
• 🤔 여기서 시간을 어떻게 더 줄이지?
  • 1부터 몫이 n과 같아지는 자연수까지 모두 찾아보기 때문에 오래 걸림 = O(n)꼴로 비교
  • 생각해 보니 N의 최댓값이 2,000,000이라고 했기 때문에 최댓값이 들어오면 몇백만개의 수를 일일이 비교하게 된다
  • 우리가 필요한 것은 ‘몫과 나머지가 같은' 수 뿐이고, 조건도 자연수로 한정되어 있으므로 처음부터 몫과 나머지와 같은 수만 구하자. ( 풀이2 )

풀이2

// 메모리초과
let n = Int(readLine()!)!
var 몫과나머지 = 1
var answers: [Int] = []
while true {
    let number = n * 몫과나머지 + 몫과나머지
    print(number)
    answers.append(number)
    몫과나머지 += 1
    if 몫과나머지 == n {
        break
    }
}
print(answers.reduce(0) { $0 + $1 })

• 몫과 나머지가 같은 수 = N * 1 + 1, N * 2 + 2, N * 3 + 3 … 의 꼴이다
• 따라서 몫과나머지를 1씩 증가시키며 위 공식에 따라 ‘몫과 나머지가 같은 수'를 구한다
• 🤔 이번엔 메모리초과가 떴다.
  • 메모리초과는 대표적으로 배열을 너무 길게 사용할 때 뜬다고 한다
  • 생각해 보니 answer를 구하는 데 배열에 넣고 그것을 합할 필요가 없어, 그냥 숫자로 변경했다

풀이3

// 런타임에러
let n = Int(readLine()!)!
var 몫과나머지 = 1
var answer = 0
while true {
    let number = n * 몫과나머지 + 몫과나머지
    answer += number
    몫과나머지 += 1
    if 몫과나머지 == n {
        break
    }
}
print(answer)

• 구해진 ‘몫과 나머지가 같은 수'를 answer에 바로 더한다
• 🤔 이번엔 런타임에러가 떴다.
  • 배열도 안 썼는데 왜 런타임에러가 뜨지?
  • 채점이 안 되는 것도 아니고, 96%정도 됐을 때 런타임에러 발생
  • 혹시나 해서 break타이밍을 앞당기고, 이를 위해 몫과나머지를 0부터 시작해 보았다 ( 풀이4 )

풀이4 (맞았습니다)

let n = Int(readLine()!)!
var 몫과나머지 = 0
var answer = 0
while true {
    몫과나머지 += 1
    if 몫과나머지 == n {
        break
    }
    let number = n * 몫과나머지 + 몫과나머지
    answer += number

}
print(answer)

최종적으로 답으로 제출해 맞은 코드는 이렇게 되었다.

풀이 3에서 런타임에러가 왜 발생했는지는 아직도 정확히 모르겠지만..

아마 while문 내의 break 타이밍이 앞에 있지 않아서? 라고 추측해 보았다.