NEVER ENOUGH

algospot.com :: POLY폴리오미노 문제 정보 문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로algospot.com 소요 시간: 1시간 2분해결: O풀이세로로 단조 폴리노미오라는 조건을 처음 봤을 때는 까다로운 제한 조건인 줄 알았지만알고보니 같은 행에 놓인 블럭들이 서로 떨어진 경우를 고려하지 않아도 된다는 뜻이었습니다.덕분에 문제에 'K개 블럭으로 구성된 폴리노미오 중 현재 행에 M개의 블럭을 놓는 경우의 수를 세는 문제'로 접근을 할 수 있지요.우리는 폴리노미오의 각 행에 몇 개의 블럭을 놓을지와 각 행을 조립하는 방법만 생각하면 됩니다. 단 두 개의 행끼리 조합하..

https://algospot.com/judge/problem/read/NUMB3RS소요 시간: 1시간 16분해결 여부: 여풀이박사가 지금 마을 u에 있고, 마을 u가 n개의 마을과 연결되어 있다면, 그 중에 하나에 방문할 확률은 1/n입니다.그런데 박사가 지금 u에 있을지 없을지는 확률적입니다.그래서 실제 확률은 (d일 째에 마을 u에 방문해있을 확률) / n으로 생각하면 되겠네요. 반대로 마을 v에 연결된 마을에서 v를 방문할 확률은 각 마을에서 v를 방문할 확률의 합이겠죠.예를 들어 v가 마을{1, 3, 4}와 연결 되어있다면 v가 방문당할(?) 확률은'1에서 v를 방문할 확률 + 3에서 v를 방문할 확률 + 4에서 v를 방문할 확률'입니다. 각 방문할 확률을 곱한다면 어떤 경우일까요.그건 각 마을..

algospot.com :: ASYMTILING비대칭 타일링 문제 정보 문제 그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은algospot.com풀이문제에서는 'n 길이의 직사각형을 채우는 방법의 수'에서 '대칭인 경우의 수'를 빼서 그 수를 구합니다. '대칭인 경우의 수'는 어떻게 구할까요?직사각형을 중앙에서 반으로 나누었을 때, 한 쪽 반에서 가능한 모든 배치는 반대쪽 반에서 대칭 형태로 나타날 수 있습니다.즉, '반 쪽 길이의 직사각형을 채우는 방법의 수'가 곧 '대칭인 경우의 수'라고 생각할 수 있겠네요. 그렇다면 n 길이와 그 절반 길이의 직사각형을 타일링하는 수를 각각..