[C/C++] 프로젝트 오일러 #85 Counting Rectangles(Brute Force)

이번 문제는 난이도는 15% 정도입니다.

문제 자체가 어려운 것은 아니어서, 보통은 단순한 방법으로 풀어보고, 알고리즘 효율을 꾀하는 편이긴 하지만, 여기서는 단순한 방법으로 문제를 풀어보았습니다.

 

counting rectangles

 

문제의 출처는 다음과 같습니다.

https://projecteuler.net/problem=85

 

이 프로그램은 Project Euler의 문제 85를 해결하기 위한 C/C++ 프로그램입니다. 문제의 목표는 주어진 제한 조건 하에서 사각형의 개수를 계산하는 것입니다. 이 코드는 특정 사각형 수와 목표 값 사이의 오차가 가장 작은 직사각형의 크기를 찾으려고 합니다.

 

//------------------------------------------------
//    Project Euler #85 - Counting rectangles
//        - by Aubrey Choi
//        - created at 2015-10-15
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>

void solve1()
{
    int nrow = 1, ncol = 1, nerror = 1999999;
    for( int row = 1 ; row < 1000 ; row++ )
    {
        for( int col = row ; col < 1000000 ; col++ )
        {
            int sum = 0;
            for( int i = 1 ; i <= row ; i++ )
            {
                for( int j = 1 ; j <= col ; j++ )
                {
                    sum += i*j;
                }
            }
            int error = sum - 2000000;
            if( error > 2000000 + nerror ) break;
            if( nerror > abs(error) ) { nrow = row; ncol = col; nerror = abs(error); }
        }
    }

    printf("Ans = %dx%d=%d, e=%d\n", nrow, ncol, nrow*ncol, nerror);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}

코드 구조 설명

1. 변수 선언:
   • nrow와 ncol은 최적의 직사각형의 행(row)과 열(column) 크기를 저장합니다.
   • nerror는 목표 사각형 개수(2,000,000)와 현재 사각형 개수 간의 오차를 나타냅니다.
2. 중첩 루프 구조:
   • 첫 번째 루프는 행(row)의 크기를, 두 번째 루프는 열(col)의 크기를 조정합니다.
   • 행의 크기는 1에서 999까지 반복되고, 열의 크기는 행 크기부터 1,000,000까지 반복됩니다. 이 루프는 대칭적이므로 열의 크기를 행보다 작게 유지할 필요가 없습니다.
3. 사각형 개수 계산:
   • 중첩된 두 개의 루프가 각 행(i)과 열(j)의 곱을 더해서 사각형의 총 개수를 계산합니다.
4. 오차 계산 및 최소 오차 찾기:
   • 목표값과 실제 계산된 사각형 수의 차이를 계산합니다.
   • 오차가 이전 최소 오차(nerror)보다 작다면, nrow, ncol 및 nerror 값을 업데이트합니다.
5. 출력:
   • 최적의 직사각형의 크기(nrow x ncol)와 해당 오차를 출력합니다.
6. 시간 측정:
   • 프로그램의 실행 시간을 측정하고 출력합니다.

주요 개선 사항

이 프로그램은 반복문을 이용해 모든 경우의 수를 검사하는 브루트 포스 방법을 사용합니다. 이 방법은 매우 느릴 수 있으며, 성능 최적화를 위해 다른 접근 방식을 고려할 수 있습니다.