프로그래머스 lv 2. 42842 카펫 c++

https://school.programmers.co.kr/learn/courses/30/lessons/42842

 

#include <bits/stdc++.h>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    double a= (brown+4)/2; //a = x+y; 이때 x>=y;
    double b=brown+yellow; // b = x*y;
    // cout<<a<<" :a ||"<<b<<" :b "<<'\n';
    // cout<<a*a-4*b<<'\n';
    // cout<<a/2<<'\n';//a가 int로 선언되어 있으면, 이 값이 3.5가 아니라 3으로 연산된다.
    // cout<<sqrt(a*a-4*b)/2<<" :sqrt(a*a-4*b) 값"<<'\n';
    int x=sqrt(a*a-4*b)/2+a/2;
    int y=b/x;
    answer.push_back(x);
    answer.push_back(y);
    
    return answer;
}

일단 위의 풀이는 내가 처음에 생각한 풀이를 통해서 구현한 방법인데, 

그냥 x+y = a, x*y= b; 라는 값을 얻었을때 그 두 값을 이용해서 x에 대한 2차방정식을 풀고, 그 2차방정식의 해에서 x의 값이 y의 값보다 크거나 같을때의 상황을 이용해서 답을 구하는 과정이다. 

수학적인 해를 구하는 과정을 코드로 옮긴 것이고, 이때에 주의해야 할 점은, int 로 a를 선언해버리면, a/2의 값이 3.5 같은 경우가 되었을때 그대로 3으로 나와버린다는 것이다. 그렇게 되버리면 a/2 과 같은 연산이 들어가는 식은 소수 부분은 다 잘려나가서 연산이 틀리게 된다. 그래서 위의 풀이에서 a, b를 double 로 선언해서 그러한 생략되는 부분이 없도록 만들어서 문제를 해결했다. 

int x, int y 라고 할때도 동일한 의문을 제기할 수 있으나, 이 문제의 경우 x(가로) , y(세로) 의 경우들이 모두 3이상의 자연수로 주어질 것이기 때문에 결과에 문제가 될만한 사항이 나오지 않는다. 

 

근데 위의 형태로 코드를 작성하면 실수부를 고려해야 하는 형태의 코드가 나와서 조금 까다로워지고 너무 수학적으로 생각해서 컴퓨터를 통한 더욱 단순한 연산을 빠르게 수행할 수 있는 능력을 제대로 사용하지 못하는 형태의 코드를 작성한다고 생각한다. 

 

이에 다른 사람의 풀이를 첨부해서 어떻게 더 단순하게 문제를 해결했는지 배워보도록 하겠다. 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int red) {

    int len = brown / 2 + 2;

    int w = len - 3;
    int h = 3;

    while(w >= h){
        if(w * h == (brown + red)) break;

        w--;
        h++;
    }

    return vector<int>{w, h};
}

위 풀이의 경우 가장 추천을 많이 받은 풀이인데, 

이때에 이 풀이를 설명해보자면, w + h = len 인 상황에서, 

가장 낮은 h의 값이 3이니까, w=len-3; h=3; 인 상황에서 시작해서, h를 1씩 증가 w를 1씩 감소 시키면서

해당 값에 해당하는 w, h 값들이 w*h = brwon+red(이때 이 문제에서는 red로 주어졌다. 나중에 yellow로 바꾼것) 을 만족하는지(이때에 brown+red는 전체 넓이와 같아) 차례로 확인해 가고, 그 부분을 만난다면 break; 하고 while문을 빠져 나와서 그때의 w, h를 출력하는 형태의 코드이다. 이때에 while 문을 w>=h 인 동안 돌리는 이유는 문제에서 주어진 상황이 가로가 세로보다 크거나 같은 상황이기 때문이다. 

아주 멋진 풀이라고 생각한다. 최소의 높이 h에서 시작해서 쭉 상황을 바꿔나가면서 w * h 의 값을 만족시키는 값을 컴퓨터의 빠른 단순연산 처리 속도를 이용해서 구하고 있다. 

 

물론 나처럼 2차방정식을 풀어서 해도 되지만, 컴퓨터를 이용하는 방법을 고려해보았을때, 머리로 2차방정식을 풀어서 근을 코드로 표현하는 것보다는, 위와 같은 형태로 코드를 작성해서 컴퓨터에게 일을 맡기는것이 더 좋을 상황이었다. 

 

위의 코드를 현재의 문제에 맡게 다른 사람이 작성한 형태의 코드를 다시 첨부해보겠다. 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;

    int x=2;
    int y=brown/2-x;

    while(1){
        if((x-1)*(y-1)==yellow)
            break;
        x++;
        y--;
    }

    answer.push_back(y+1);
    answer.push_back(x+1);
    return answer;
}

아주 깔끔하다. 

 

2차방정식을 이용한 풀이를, 다른 사람이 풀이한 방법을 한번 첨부해보겠다. 내가 작성한 것보다 더욱 깔끔하게 표현한것 같다. 

#include <vector>
#include <cmath>
using namespace std;

vector<int> solution(int brown, int yellow) {
    int x, y;   //2차방정식의 해로 품.
    x= 0.5*((2+brown/2)+sqrt((2+brown/2)*(2+brown/2)-4*brown-4*yellow));
    y=  0.5*brown-x+2;
    return {x,y};
}

 

위의 풀이는 중간 과정을 int 로 담아내지 않기 때문에 결국 마지막에만 int로 담아내는 형태의 풀이기 때문에 내가 맨 위에 적었던 것처럼 

double로 선언하지 않아도 되서 오히려 더욱 깔끔하게 해결해낼 수 있는 부분이라 생각한다.