이 페이지는 코딩도장 데이터의 읽기 전용 정적 보관본입니다.

농장 분할

밥 아저씨는 돈을 힘들게 모은 끝에 한 토지를 구입했다.

밥 아저씨는 그 토지에 유명한 식물을 심을려고 하는데,

그 식물은 주변 √n 미터 안에 다른 식물이 있으면 자라지 못한 다고 한다.

그러므로 토지의 넓이를 n으로 나누어야 한다.

토지의 가로와 세로의 길이를 입력받을때, 최대 심을 수 있는 식물의 개수는?

(단, n의 값은 식이 성립하는 n의 범위 중에서 최대여야 한다.)

예)

640  400

1980 640

답)

40

3168

단 반드시 그 나무를 중심으로 한 √n 영역이 필요하다. 그리고 그 영역이 다른 영역과 겹치면 안된다.

재귀함수

2018/05/27 22:00

김영성

문제가 이해하기 어렵네요, 좀 더 쉽게 문제를 설명해 주세요. - pahkey, 2018/05/28 09:16
제가 이해한 바로는....식물하나가 자라는데 n x n 크기의 당이 필요하고... 답으로 유추해보건데 남는땅이없어야 하는 거 맞죠? n 을 두 수의 최대공약수로 두고 풀라는 말 같은데 맞나요? - Hyuk, 2018/05/28 10:08
- 김영성, 2018/05/29 20:52
문제의 표현이 조금 애매합니다. 나무 한 그루를 심기 위해서는 1. 반드시 그 나무를 중심으로 한 n*n 크기의 영역이 필요하다. 2. 그 영역이 다른 나무의 영역과 겹치지 않아야 한다. 라는 말이 추가되면 좋겠습니다. 그렇지 않으면 꼭지점에도 심을 수 있기 때문에, 예를 들어 6*4 에서 2*2로 나눠 6 그루가 아니라 각 정사각형의 꼭지점과 무게중심을 모두 더해서 18그루를 심을 수 있습니다. - Noname, 2018/09/08 01:02
+1 그렇게 생각할 수도 있군요 수정 하였습니다 - 김영성, 2018/09/08 17:35

38개의 풀이가 있습니다.


다시 올립니다. 
    public static int SqureBoard(int length, int height)
    {

        if(length>height)
        {
            length = length-height;
        }
        else if(length<height)
        {
            height = height-length;
        }
        else
        {
            return length;
        }

        return SqureBoard(length,height);
    }

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int l = 640, h =400;
        int a = SqureBoard(l,h); // a=80
        int squre = (l/a)*(h/a);    //흠....
        System.out.print(squre);

    }

}

2018/05/31 20:42

박용훈

from math import gcd

n1, n2 = 1980, 640
print(n1 * n2 // gcd(n1, n2)**2)

2018/06/06 01:51

재즐보프

public static void main(String[] args) {
        int a = 1980;
        int b = 640;
        System.out.println((a * b) / (int) Math.pow(gcd(a, b), 2));
    }

    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

2018/09/02 21:12

김지훈

파이썬입니다.

a, b = tuple(map(int, input('토지의 가로 세로 길이를 입력하세요 ex) 120 260 \n 입력 : ').split()))
c = a*b
while a: a, b = max(a, b) % min(a, b), min(a, b)   # n = gcd(a, b) = b
print(c/b**2)             # result = a/gcd(a,b) * b/gcd(a,b) = a*b / gcd(a,b)**2

결과

토지의 가로 세로 길이를 입력하세요 ex) 120 260 
 입력 : 1980 640
3168.0

2018/05/28 10:24

Hyuk

파이썬으로

import re

a, b = [int(x) for x in re.findall("[0-9]+", input("토지 너비*길이를 입력하세요: "))[:2]]  # 첫 두 개의 정수를 a,b에

gcd = lambda x,y: x if x == y else gcd(max(x, y)-min(x,y), min(x,y))  # 최대공약수 (유클리드)

print("%d" % (a/gcd(a,b) * b/gcd(a,b)))

2018/05/28 13:59

Gene Byun

#include <stdlib.h>
#include <stdio.h>

int min( int x, int y )
{
    if( x <= y ) return x;
    else return y;
}

int max( int x, int y )
{
    if( x >= y ) return x;
    else return y;
}

int main(int argc, char * argv[])
{
    int i, num;
    int x = atoi(argv[1]);
    int y = atoi(argv[2]);
    int max_common_divisor = 1;
    int min_num = min(x,y);
    int max_num = max(x,y);

retry:
    num = max_num % min_num;
    if( num == 0 )
    {
        max_common_divisor = min_num;
    }
    else
    {
        max_num = min_num;
        min_num = num;
        goto retry;
    }

    printf("max common divisor : %d\n", max_common_divisor);
    printf("plant number : %d\n", (x * y) / (max_common_divisor*max_common_divisor));
    return 0;
}

2018/06/20 08:41

구름과비

def gcd(a, b):
    if a < b: a, b = b, a
    while b: a, b = b, a % b
    return a

w = int(input('농장 가로 길이: '))
h = int(input('농장 세로 길이: '))
n = gcd(w,h)
print('최대식물수: {}'.format(w/n*h/n))

2018/06/26 01:25

Creator

using System;
using System.Collections.Generic;
using System.Linq;

namespace CD169
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("토지의 가로 세로 길이 입력 (ex. 640 400): ");
            // split on whitespace
            var input = Console.ReadLine()
                .Split(new char[0], StringSplitOptions.RemoveEmptyEntries).ToList(); 
            var landSize = new List<int>();
            input.ForEach(item => landSize.Add(int.Parse(item)));

            int a = landSize.Max(), b = landSize.Min();
            int landArea = a * b, plantArea = GCD(a, b) * GCD(a, b);
            Console.WriteLine((int)(landArea/plantArea));
        }

        // a, b (a > b)의 최대공약수(유클리드 호제법)
        static int GCD(int a, int b)
        {
            if (b == 0) { return a; }
            else { return GCD(b, a % b); }
        }
    }
}

2018/06/27 09:34

mohenjo

최대공약수 함수는 써보고 싶지 않아서.......

def square(a,b):
          Max = max(a,b)
          Min = min(a,b)
          n = Max%Min
          if n != 0:
                    square(Min,n)
          else:
                    print(Min)

2018/07/10 22:18

김영성

가로3,세로6 일 경우, n=3 이 되어서 반경 3×3 = 9 이내에는 작물을 심을 수 없어야 하는데 가로3세로6인 땅에는 길이 9는 존재 못하는게 아닌가요?? 저의 읽기능력이 좋지 못하여서 리해가 잘 안 되네요 T.T - 암살자까마귀, 2019/05/03 10:32
한 변의 길이가 3이아닌 √n, sqrt(3)을 의미하는 거랍니다. 이문제는 최대공약수 문제이니 참고하시면 좋겠네요 - 김영성, 2019/05/03 18:32
글을 다시보니 오해할만한 소지가 충분했네요. 수정하였고 오류 알려주셔서 감사합니다. - 김영성, 2019/05/03 18:33
from math import gcd

a, b = 1980, 640
print(a * b // gcd(a, b)**2)
5

2018/08/13 14:35

S.H

// ========================================
        int num1 = 640;
        int num2 = 400;

        int a = gcd(num1, num2);
        System.out.println((num1 * num2) / (a * a));
    }

    public static int gcd(int a, int b) {

        while (b != 0) {

            int temp = a % b;
            a = b;
            b = temp;

        }
        return Math.abs(a);
    }

2018/09/02 21:13

채규빈

def num_plant(x, y):
    G = gcd(x, y)
    return (x // G) * (y // G)

2018/09/08 00:54

Noname

import java.util.Scanner;
public class GCD {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
            System.out.print("첫번째 값 : ");       
            int fir = input.nextInt();
            System.out.print("두번째 값 : ");       
            int sec = input.nextInt();
        for (int i = Math.min(fir,sec);i>0;i--){
            if ((fir%i==0)&&(sec%i==0)){
            System.out.println(i);
            break;

            }
        }
    }
}

2018/10/01 16:03

잭Jack

number = list(map(int, input("두 자연수 입력 : ").split()))
big_box = []
for i in number :
    small_box = []
    x = 2
    while i > 1 :
        if i % x == 0 :
            i = i // x
            small_box.append(x)
        else : x += 1
    big_box.append(small_box)
    print(small_box)
print(big_box)
big_box.append(set(big_box[0]+big_box[1]))
print(big_box)

tmp = 1
for i in big_box[2] :
    if i in big_box[0] or big_box[1] :
        tmp *= (i**min(big_box[0].count(i), big_box[1].count(i)))
print(tmp)
print((eval('*'.join(map(str,big_box[0]))) / tmp) * (eval('*'.join(map(str,big_box[1]))) / tmp))

2019/01/03 22:41

lucky1to10

import math


area = input("'가로 세로'식으로 입력 ").split()


def divisor_make(n):
    divisor_list = set()
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisor_list.add(i)
            divisor_list.add(n//i)
    return divisor_list


max_divisor = max(divisor_make(int(area[0])) & divisor_make(int(area[1])))

print(int(int(area[0])/max_divisor)*int(int(area[1])/max_divisor))


2019/01/11 22:09

농창

num=input("가로 세로를 입력하시오:")
num_arr=list(num.split())
for x in range(0,len(num_arr)):
    num_arr[x]=int(num_arr[x])
if num_arr[0]%2==0 and num_arr[1]%2==0:
    while num_arr[0]%2==0 and num_arr[1]%2==0:
        num_arr[0]=num_arr[0]/2
        num_arr[1]=num_arr[1]/2
if num_arr[0]%3==0 and num_arr[1]%3==0:
    while num_arr[0]%3==0 and num_arr[1]%3==0:
        num_arr[0]/=3
        num_arr[1]/=3
if num_arr[0]%5==0 and num_arr[1]%5==0:
    while num_arr[0]%5==0 and num_arr[1]%5==0:
        num_arr[0]/=5
        num_arr[1]/=5
if num_arr[0]%7==0 and num_arr[1]%7==0:
    while num_arr[0]%7==0 and num_arr[1]%7==0:
        num_arr[0]/=7
        num_arr[1]/=7   
print(int(num_arr[0]*num_arr[1]))

2019/01/15 20:18

빅디펜스

import math
a, b = map(int,input().split())
num = math.gcd(a, b)
print(int((a/num) * (b/num)))

2019/01/22 15:44

D.H.

N1 = int(input("농장의 가로길이 : "))
N2 = int(input("농장의 세로길이 : "))

def gcd(a, b) :
    if a > b :
        (a, b) = (b, a)
    while b != 0 :
        (a, b) = (b, a % b)
    return a

result = N1 * N2 / (gcd(N1, N2) * gcd(N1, N2))

print(round(result))

파이썬입니다

2019/02/15 20:47

임민주

def gcd(a, b):
    if a < b:
        return gcd(b,a)
    if a%b== 0:
        return b
    return gcd(b, a%b)

def square(a, b):
    g = gcd(a, b)
    n = (a*b)/(g*g)
    print(n)

w, h =map(int,input('가로와 세로를 입력하세요: ').split(' '))
square(w, h)

2019/06/06 13:24

Hwaseong Nam

list_0 = list(map(int, input().split()))
def Function(num):
    share = []
    while num > 1:
        for i in range(2, num+1):
            if num%i == 0:
                share.append(i)
                num = num//i
                break
    return share
set_1 = set()
list_1 = []
list_2 = []
list_3 = []
dict = {}
for i in list_0:
    a = Function(i)
    set_1 = set_1 | set(a)
    list_1.append(a)

for i in set_1:
    for j in range(len(list_1)):
        list_2.append(list_1[j].count(i))
    list_3.append(int(min(list_2)))
    list_2 = []
set_1 = list(set_1)
for i in range(len(set_1)):
    dict[set_1[i]] = list_3[i]
result = 1
for i in dict.keys():
    result *= i**dict[i]
print(int((list_0[0]*list_0[1])/(result**2)))

파이썬코드의 장점이 사라진 코드...

2019/09/06 16:50

이명운

def gcd(a,b):
    value = min(a,b)
    while True :
        if a % value ==0 and b % value ==0:
            return value
        else :
            value -= 1

cd1 = int(input("농장 가로 입력 : "))
cd2 = int(input("농장 세로 입력 : "))
gcd_value = gcd(cd1,cd2)
result = int(cd1/gcd_value * cd2/gcd_value)
print(result)

2019/10/13 01:21

semipooh

#include <math.h>
int the_greatest_common_denominator(int a,b)
{
int result = 1;
int ArraySizeCount1 = 0, ArraySizeCount2 = 0;
int *a_denominator_Array = new int;
int *b_denominator_Array = new int;
while(a!=1)
{
for(int i =2; i<a;i++)
{
a%i == 0 ? a = a/i, a_denominator_Array[i]++ , i>ArraySizeCount1? ArraySizeCount1=i:0; : 0;
}
}
while(b!=1)
{
for(int i =2; i<b;i++)
{
b%i == 0 ? b= b/i, b_denominator_Array[i]++ , i>ArraySizeCount2? ArraySizeCount2=i:0; : 0;
}
}
int count = 0;
sizeof(a_denominator_Array) > sizeof(b_denominator_Array) ? count = sizeof(a_denominator_Array)/ sizeof(int): count = sizeof(b_denominator_Array)/ sizeof(int) ; 

for(int i =2;i<count;i++)
{
a_denominator_Array[i] > b_denominator_Array[i] && b_denominator_Array[i] >0 ? result*=(int)pow(i,b_denominator_Array[i]): 0;
b_denominator_Array[i] > a_denominator_Array[i] && a_denominator_Array[i] >0 ? result*=(int)pow(i,a_denominator_Array[i]): 0;
}
}
delete a_denominator_Array,b_denominator_Array;
return result;
}

2019/12/23 23:56

Anderson

h=int(input("가로의 길이를 입력하십시오: "))
v=int(input("세로의 길이를 입력하십시오: "))
# 두 수의 최대 공약수를 찾아서 가로, 세로를 각 각 나눈 결과를 곱하면 됨.
n=1
lst=[]
while n<v:
    if h%n==0 and v%n==0:
        lst.append(n)  #max(lst)가 최대 공약수
    n+=1
print(int((h/max(lst))*(v/max(lst)))) #(가로/최대공약수) x (세로/최대공약수)

2019/12/30 02:10

박시원

a = int(input("가로:"))

b = int(input("세로:"))

gongyaksu=[]

for i in range(1, min(a,b)+1):

    if a%i ==0 and b%i == 0:

        gongyaksu.append(i)

    else: continue


print(int((a/max(gongyaksu))*(b/max(gongyaksu))))

2020/02/10 00:23

HyukHoon Kim

from math import gcd

a = int(input()) b = int(input())

A = gcd(a, b) B = (ab)//(A*2) print(B)

2020/02/21 13:21

이국성

def sep(a, b):
    for i in range(1, min(a, b)+1):
        if a%i==0 and b%i==0:
            max=i
    return a*b/max**2

2020/03/12 16:04

Caplexian _

def cal_plants_num(x, y):
    area = x * y
    gcd = max([i for i in range(1, max(x, y)) if x % i == 0 and y % i == 0])

    result = area // gcd ** 2
    return result


# answer: 40
case1 = 640, 400

# answer: 3168
case2 = (1980, 640)

if __name__ == "__main__":
    print(cal_plants_num(640, 400))
    print(cal_plants_num(1980, 640))

2020/03/30 15:20

inca1735

import java.util.ArrayList;
import java.util.Scanner;

public class Q168{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        ArrayList<Integer> input = new ArrayList<Integer>();
        System.out.print("a? : ");
        input.add(scan.nextInt());
        System.out.print("b? : ");
        input.add(scan.nextInt());
        int temp;
        for(int i=2;; i++) {
            temp = input.get(i-2)%input.get(i-1);
            if(temp!=0) {
                input.add(temp);
            } else {
                break;
            }
        }

        System.out.println(input.get(0)*input.get(1)/(int)Math.pow(input.get(input.size()-1), 2));
    }
}

2020/05/11 18:23

Daniel Park

from math import gcd

class GetNumPlant:
    def __init__(self):
        self.num = 0
    def calNum(self,w,h):
        self.num = w*h/gcd(w,h)**2
        print (self.num)

a = GetNumPlant()
a.calNum(640,400)

2020/11/04 22:29

footsize

def sosu(num):
    result = []

    for i in range(1,int(num)+1):
        if int(num) % i == 0:
            result.append(i)

    if len(set(result)) == 2:
        return True


def insu(num):
    temp = int(num)
    result = []
    result2 = []
    while temp != 1:
        for i in range(2,temp+1):
            if temp % i == 0 and sosu(i):
                result.append(i)
                temp = temp // i

    result.sort()
    result1 = list(set(result))
    result1.sort()

    for aa in result1:
        count = 0
        for bb in result:
            if bb == aa:
                count += 1
        result2.append(count)

    return [result1, result2]

def part(num):
    ins = []
    full = {}

    for aa in insu(num)[0]:
        if aa not in ins:
            ins.append(aa)
            full[aa] = insu(num)[1][insu(num)[0].index(aa)]

        if insu(num)[1][insu(num)[0].index(aa)] > full[aa]:
            continue

    return full

def gcd(a,b):
    _a = part(a)
    _b = part(b)
    result = {}

    for i in _a.keys():
        if i in _b:
            result[i] = min(_a[i],_b[i])
        else:
            result[1] = 1

    mult = 1
    for j in result.keys():
        mult = mult*(j**result[j])

    return mult

n1 = 1980
n2 = 640
print(n1/gcd(n1,n2)*n2/gcd(n1,n2))

2020/11/20 08:46

DSHIN

from math import *

farm=input("write your farm [a,b] :")

for_farm=farm.split(",")

ggccdd=gcd(int(for_farm[0]),int(for_farm[1]))

first=int(for_farm[0])/ggccdd

second=int(for_farm[1])/ggccdd

print(first*second)

2020/12/06 20:34

전준혁

def farm(a, b):
    c = max(set([i for i in range(1, a + 1) if a % i == 0]) & set([i for i in range(1, b + 1) if b % i == 0]))
    return (a/c) * (b/c)


print(farm(640, 400))
print(farm(1980, 640))

2020/12/08 17:31

김우석

from math import gcd
a = input().split(" ")
a1,a2 = int(a[0]),int(a[1])
new_gcd = gcd(a1,a2)

print(a1//new_gcd * a2//new_gcd)

2021/02/14 18:05

개촙오

x=int(input('가로'))
y=int(input('세로'))

common=[]

for i in range(1,x+1):
    if x % i == 0 and y % i == 0:
        common.append(i)

big=common[-1]

print(int((x/big) * (y/big)))

2021/03/04 10:18

최우진

def dividing_to_max(a,b):
    gcd_out = math.gcd(int(a),int(b))
    return int(int(a)*int(b)/(gcd_out**2))

2021/04/27 14:05

최태호


from math import gcd
def maxi(a,b):
    length = gcd(a,b)
    return print((a/length)*(b/length))

2021/05/16 11:19

ss2663

#codingdojing_farm_partition

#각 변의 최대공약수를 구한뒤 최종 넓이에서 나누어 준다.

def gcd(a, b):  #a/b = q r , b/r이 0인 r의 값

    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)

a, b = map(eval,input('a, b: ').split(','))

com = gcd(a,b)
print(a/com * b/com)

2021/10/17 18:57

Jaeman Lee

def split_the_farm(h,v):
    n=1
    lst=[]
    while n < v:
        if h%n==0 and v%n==0:
            lst.append(n)
        n+=1
    return int((h*v/max(lst)**2))

if __name__ == '__main__':
    h=int(input("가로의 길이를 입력하십시오: "))
    v=int(input("세로의 길이를 입력하십시오: "))
    print(split_the_farm(h,v))

2021/11/02 19:24

서현준

목록으로