백준 9196번 [정수 직사각형](C++) -yes6686- 티스토리

백준 문제 풀이: 9196

---

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

문제 설명:

주어진 직사각형의 높이와 너비를 기준으로 현재 대각선 길이보다 크면서 가장 작은 대각선을 가지는 새로운 직사각형을 찾는 문제입니다. 이때, 같은 대각선 길이를 가진다면 더 작은 높이를 우선시합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

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

    while (true) {
        int h, w;
        cin >> h >> w;
        if (h == 0 && w == 0) break; // 종료 조건

        int curDiagonal = h * h + w * w; // 현재 직사각형의 대각선 제곱
        int maxDiagonal = 20001;        // 최대 대각선 값
        int nh = 0, nw = 0;             // 다음 직사각형의 높이, 너비

        // 가능한 모든 직사각형 탐색
        for (int i = 1; i <= 150; i++) {
            for (int j = i + 1; j <= 150; j++) { // i < j 조건으로 중복 계산 제거
                int diagonal = i * i + j * j;   // 대각선 제곱 계산

                // 조건 1: 대각선 길이가 동일하고 더 큰 h를 찾는 경우
                if (diagonal == curDiagonal && h < i) {
                    nh = i;
                    nw = j;
                }
                // 조건 2: 대각선 길이가 현재 대각선보다 크고 최소 대각선을 찾는 경우
                else if (diagonal > curDiagonal && diagonal < maxDiagonal) {
                    maxDiagonal = diagonal;
                    nh = i;
                    nw = j;
                }
                // 조건 3: 대각선 길이가 동일한 경우 더 작은 h를 우선
                else if (diagonal == maxDiagonal && i < nh) {
                    nh = i;
                    nw = j;
                }
            }
        }
        cout << nh << ' ' << nw << '\n'; // 결과 출력
    }
    return 0;
}

---

코드 설명

위 코드는 가능한 모든 직사각형의 조합을 탐색하여 조건에 맞는 직사각형을 찾는 방식으로 동작합니다. 이중 반복문 탐색과 조건 평가를 통해 최적화된 결과를 도출합니다. 주요 알고리즘은 다음과 같습니다:

1. 현재 대각선과 동일한 값을 찾을 때, 높이가 더 큰 직사각형을 우선합니다.
2. 현재 대각선보다 큰 값 중 최소 대각선을 탐색합니다.
3. 동일한 대각선일 경우, 높이가 더 작은 직사각형을 선택합니다.

---

결과

위 코드를 통해 문제를 효율적으로 해결할 수 있었습니다. 완전 탐색 알고리즘을 활용해 모든 가능한 직사각형을 탐색하며, 조건에 맞는 최적의 값을 도출했습니다. 다른 개선 사항이 있다면 댓글로 공유 부탁드립니다!