[완전 탐색] 백준 브론즈1 10448번: 유레카 이론(Swift)

https://www.acmicpc.net/problem/10448

10448번: 유레카 이론

Code

let testCase = Int(readLine()!)!

M: for _ in 0..<testCase {
  let k = Int(readLine()!)!
  var x = 0
  var Tn = [0]
  for n in 1...45 {
    if k < n * (n + 1)/2 {
      x = n
      break
    }
    Tn.append(n * (n + 1)/2)
  }
  for f in 1..<x {
    for s in f..<x {
      for t in s..<x {
        if Tn[f] + Tn[s] + Tn[t] == k {
          print(1)
          continue M
        }
      }
    }
  }
  print(0)
}

풀이과정

주어진 K을 삼각수 3개로 표현이 되는지를 찾는 문제이기 때문에 탐색 문제로 볼 수 있다.

때문에 삼각수를 담고 있는 배열을 먼저 만들어 줘야 계산하기가 편하다.

K의 범위는 3 ≤ K ≤ 1,000이다.

즉, 삼각수 Tn의 n 범위는 1 ≤ n ≤ 45가 된다.

때문에, 배열 Tn은 45의 삼각수의 값까지 만들어 주면 되는데 여기서 경우의 수를 줄이기 위해

주어진 K에 따라 배열 Tn을 만들어 준다.

예를 들어 K가 9라고 한다면, 4의 삼각수 보다 K가 작기 때문에 3의 삼각수까지만, 탐색해 주면 된다.

이처럼, K를 삼각수와 비교하여 탐색할 경우의 수를 줄여 실행 시간을 줄일 수 있다.

탐색의 경우 3자리를 탐색해야 하기 때문에 3중 for 문을 사용한다.

여기서 큰 의미는 없지만, T가 1, 1, 2나 1, 2, 1의 결과값은 같기 때문에 생략이 가능하다.

때문에 상위 반복 문의 값을 활용하여 그 값부터 X까지 탐색하면 중복을 최소한으로 할 수 있다.

Tip
탐색 문제는
문제를 해결하는 것을 중점으로 두고 먼저 해결 후 탐색 범위를 줄여 시간을 단축시키는 방향으로 접근하는 것이 쉽게 문제를 풀 수 있는 방법이라고 생각된다.
위 문제 같은 경우 먼저 1부터 45까지 3중 for 문을 통해 문제를 풀고 탐색 범위를 K 값을 활용해 축소시켜 문제를 풀 수 있다.
처음부터 실행 시간부터 생각하면 문제를 어렵게 접근하게 될 수도 있다.