코드포스 - Domino piling (도미노 말뚝 박기)

번역 (번역이 안맞는 부분이 있을 수 있습니다... 주의 부탁드립니다 ㅠ)

 

문제->

2 x 1 크기의 도미노 조각을 이용해 M x N 크기의 판을 채울 때, 필요한 최대 도미노 조각 수를 구한다.
이때, 도미노 조각은 서로 겹칠 수 없으며, 판 안에 존재해야 한다.

 

문제풀이->

조각의 긴 변이 높이가 되도록 세운 후, 판의 좌상단 부분부터 채웁니다.

여기서 긴 변은 2가 되고, 1 크기의 변으로 한 줄부터 채운다고 생각하면, 판의 너비와 동일하게 됩니다.
따라서, 하나의 줄을 채우는데 필요한 조각 수는 N만큼이 된다.

반복적으로 여러 줄에 대해 채울 수 없을 때까지 조각을 채우면, 반복적으로 N을 개수에 더하면 된다.

하나의 줄에 더 이상 조각을 세운 채로(긴 변이 높이가 되도록) 채울 수 없으면, 눕혀서 채운다.

조각을 눕히면 조각의 너비는 2가 되고, 판의 너비에 대해 최대로 넣는 개수는 (N / 2)의 내림 수만큼이 된다.

 

눕혀서 채우는 것을 마지막으로 개수에 더하면, 총 조각 수를 구할 수 있다.

 

 

문제 풀이 코드 ->

 

import java.util.Scanner;
public class Main 
{

    public static void main(String[] args)
    {
        
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        System.out.println((n*m)/2);
        in.close();
    }

}

 

너무 쉬워서 풀렸을때 뭐지??? 했다...