본문 바로가기

👨‍💻 코딩 도서관

domino1

코드포스 - Domino piling (도미노 말뚝 박기) 번역 (번역이 안맞는 부분이 있을 수 있습니다... 주의 부탁드립니다 ㅠ) 문제-> 2 x 1 크기의 도미노 조각을 이용해 M x N 크기의 판을 채울 때, 필요한 최대 도미노 조각 수를 구한다. 이때, 도미노 조각은 서로 겹칠 수 없으며, 판 안에 존재해야 한다. 문제풀이-> 조각의 긴 변이 높이가 되도록 세운 후, 판의 좌상단 부분부터 채웁니다. 여기서 긴 변은 2가 되고, 1 크기의 변으로 한 줄부터 채운다고 생각하면, 판의 너비와 동일하게 됩니다. 따라서, 하나의 줄을 채우는데 필요한 조각 수는 N만큼이 된다. 반복적으로 여러 줄에 대해 채울 수 없을 때까지 조각을 채우면, 반복적으로 N을 개수에 더하면 된다. 하나의 줄에 더 이상 조각을 세운 채로(긴 변이 높이가 되도록) 채울 수 없으면, 눕혀.. 2021. 6. 25.

이전 1 다음

티스토리툴바