[PCCP] Lv2: 카펫(42842) 해설

문제

- 문제 링크: 카펫

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- N: total_size

- 한 변의 최대 길이는 sqrt(N)이므로 최종 시간 복잡도는 O(sqrt(N))

#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(int green, int white) {
  // 격자의 총 개수 (파란색 격자 + 흰색 격자)
  int total_size = green + white;
  // 세로 길이의 범위는 3부터 (파란색 격자 + 흰색 격자)의 제곱근
  for (int vertical = 3; vertical <= sqrt(total_size); ++vertical) {
    // 사각형 구성이 되는지 확인
    if (total_size % vertical == 0) {
      int horizontal = total_size / vertical; // 사각형의 가로 길이
      // 카펫 형태로 만들 수 있는지 확인
      if (green == (horizontal + vertical - 2) * 2) {
        return {horizontal, vertical}; // {가로 길이, 세로 길이}
      }
    }
  }
  return {}; // 만약 답을 찾지 못했다면 빈 벡터를 반환
}


//아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>

using namespace std;

void print(vector<int> vec)
{
  copy(vec.begin(), vec.end(), std::ostream_iterator<int>(cout, " "));
  cout << endl;
}

int main()
{
  print(solution(10, 2)); //출력값 : 4 3
  print(solution(8, 1)); //출력값 : 3 3
  print(solution(24, 24)); //출력값 : 8 6
  
  return 0;
}

solution 2)

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int y = 0;
    for (size_t x = yellow; x > 0; --x){
        y = yellow / x;
        if (2*x + 2*y + 4 == brown && x*y == yellow){
            answer.push_back(x+2);
            answer.push_back(y+2);
            break;
        }
    }
    return answer;
}

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: totalSize

- 한 변의 최대 길이는 sqrt(N)이므로 최종 시간 복잡도는 O(sqrt(N))

class Solution {
    public int[] solution(int brown, int yellow) {
        // 격자의 총 개수 (붉은색 격자 + 흰색 격자)
        int totalSize = brown + yellow;
        // 세로 길이의 범위는 3부터 (붉은색 격자 + 흰색 격자)의 제곱근
        int sqrt = (int)Math.sqrt(totalSize);
        for (int vertical = 3; vertical <= sqrt; vertical++) {
            // 사각형 구성이 되는지 확인
            if (totalSize % vertical == 0) {
                // 사각형의 가로 길이
                int horizontal = (int)(totalSize / vertical);
                // 카펫 형태로 만들 수 있는지 확인
                if (brown == (horizontal + vertical - 2) * 2) {
                    return new int[]{horizontal, vertical}; // [가로 길이, 세로 길이]
                }
            }
        }
        return new int[]{}; // 만약 답을 찾기 못했다면 빈 리스트를 반환
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: total_size

- 한변의 최대 길이는 sqrt(N)이므로 최종 시간 복잡도: O(sqrt(N))

def solution(blue, white):
    # 격자의 총 개수(파란색 격자 + 흰색 격자)
    total_size = blue + white
    
    # 세로 길이의 범위는 3부터 (파란색 격자 + 흰색 격자)의 제곱근
    for vertical in range(3, int(total_size**0.5) + 1):
        # 사각형ㅇ 구성이 되는지 확인
        if total_size % vertical == 0:
            horizontal = (int)(total_size / vertical) # 사각형의 가로 길이
            # 카펫 형태로 만들 수 있는지 확인
            if blue == (horizontal + vertical - 2) * 2:
                return [horizontal, vertical] # [가로 길이, 세로 길이]
    return [] # 만약 답을 찾기 못했다면 빈 리스트를 반환

solution 2)

def solution(brown, yellow):
    answer = []
    for x in range(yellow,0,-1):
        y = yellow // x
        if 2*x + 2*y + 4 == brown and x*y == yellow:
            return [x+2, y+2]

solution 3)

import

 

(JavaScript)

solution 1)

- N: totalSize

- 한 변의 최대 길이는 sqrt(N)

- 최종 시간 복잡도: O(sqrt(N))

function solution(yellow, white) {
    // 격자의 총 개수 (노란 격자 + 하얀 격자)
    const totalSize = yellow + white;
    
    // 세로 길이의 범위는 3부터 (노란 격자 + 하얀 격자)의 제곱근
    for (let vertical = 3; vertical <= Math.sqrt(totalSize); vertical++) {
        // 사각형 구성이 되는지 확인
        if (totalSize % vertical === 0) {
            const horizontal = totalSize / vertical; // 사각형의 가로 길이
            
            // 카펫 형태로 만들 수 있는지 확인
            if (yellow === (horizontal + vertical - 2) * 2) {
                return [horizontal, vertical]; // [가로 길이, 세로 길이]
            }
        }
    }
    
    return []; // 만약 답을 찾지 못했다면 빈 배열을 반환
}

solution 2)

import

solution 3)

import