[백준 25373] 벼락치기 (C#, C++) - soo:bak

문제 링크

25373번 - 벼락치기

설명

이 문제는 간단한 그리디 알고리즘을 사용해 주어진 조건에 따라 최소 이동 횟수를 계산하는 문제입니다.

문제 요약

• 한 번에 최대 6칸까지 이동 가능하며, 단 한 번만 추가 점프(최대 3칸)가 허용됩니다.
• 목표는 주어진 거리 n만큼 이동하기 위한 최소 이동 횟수를 구하는 것입니다.

접근법

• n이 작은 값일수록 하드코딩 처리하는 것이 더 빠르고 정확합니다.
• n이 22 이상부터는:
  • 점프(3칸)를 사용한 후 남은 거리를 7로 나누는 방식으로 계산합니다.
  • 이때 총 이동 횟수는 몫 + 3이 됩니다. (기본 점프 포함)

수학적 정리

문제 조건에 따라 다음과 같이 처리할 수 있습니다:

• n == 1 → 1
• 2 ≤ n ≤ 3 → 2
• 4 ≤ n ≤ 6 → 3
• 7 ≤ n ≤ 10 → 4
• 11 ≤ n ≤ 15 → 5
• 16 ≤ n ≤ 21 → 6
• n ≥ 22 → \(\left\lceil \frac{n'}{7} \right\rceil + 3\)

시간 복잡도

• 상수 범위 내에서 간단한 조건 분기 및 반복문이므로 O(1)입니다.

---

Code

[ C# ]

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = long.Parse(Console.ReadLine()!);

      if (n == 1) Console.Write(1);
      else if (n <= 3) Console.Write(2);
      else if (n <= 6) Console.Write(3);
      else if (n <= 10) Console.Write(4);
      else if (n <= 15) Console.Write(5);
      else if (n <= 21) Console.Write(6);
      else {
        var i = n;
        while (true) {
          if (i % 7 == 0) {
            Console.Write(i / 7 + 3);
            break;
          }
          i++;
        }
      }
    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n; cin >> n;

  if (n == 1) cout << 1;
  else if (n <= 3) cout << 2;
  else if (n <= 6) cout << 3;
  else if (n <= 10) cout << 4;
  else if (n <= 15) cout << 5;
  else if (n <= 21) cout << 6;
  else {
    ll i = n;
    while (true) {
      if (i % 7 == 0) {
        cout << i / 7 + 3 << "n";
        break ;
      }
      i++;
    }
  }

  return 0;
}