백준 10419번 [지각](C++) -yes6686- 티스토리

백준 문제 풀이: 10419 (지각)

---

문제 링크: https://www.acmicpc.net/problem/10419

문제 설명:

학생이 지각을 하면 **수업 시작 시간**을 기준으로 다음과 같은 조건이 적용됩니다: - 학생의 도착 시간 t를 만족하는 조건은 t × t + t ≤ d입니다. 여기서 d는 수업이 시작되기까지 남은 시간입니다. 이 조건을 만족하는 **최대 t**를 구해야 합니다. 여러 테스트 케이스에 대해 결과를 출력하세요.

---

문제 해결 코드

#include <iostream>
using namespace std;

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

    int T; // 테스트 케이스 개수
    cin >> T;

    while (T--) {
        int d; // 남은 시간 d 입력
        cin >> d;

        int t = 0; // 지각 시간 t 초기화
        while (t * t + t <= d) { // 조건을 만족하는 최대 t 탐색
            t++;
        }
        
        cout << t - 1 << '\n'; // 최대 t 출력 (초과된 t는 제외)
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 조건 검증: t × t + t ≤ d를 만족하는 t를 찾습니다.
• 반복문 탐색: - t를 0부터 시작해서 조건을 만족하지 않을 때까지 증가시킵니다.
• 출력 처리: - 조건을 만족하지 않는 마지막 t는 제외하고 t - 1을 출력합니다.

세부 구현:

• t * t + t <= d: 조건이 참일 때 t를 증가시킵니다.
• 최종적으로 t - 1: 최대 조건을 만족하는 값 출력

시간 복잡도 분석

• 입력으로 주어진 d에 대해 반복문은 최대 √d만큼 실행됩니다.
• 테스트 케이스 T개에 대해 전체 시간 복잡도는 **O(T ⋅ √d)**입니다.

---

결과

조건 t × t + t ≤ d를 만족하는 최대 t를 정확히 출력합니다.

• 입력 예시:

  2  
  5  
  6

• 출력 예시:

  1  
  2

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!