코테용 문제풀이/알고스팟

알고스팟 asymtiling 문제 파이썬으로 풀기

tiling 관련 문제가 다 그렇듯, 타일을 주어진 도형으로 채우는 문제이다. 타일은 겹쳐서는 안되고, 90도 회전은 가능하지만, 타일링이 좌우 대칭이어선 안된다. 대칭을 허용하지 않는다는 조건을 뺏으면 쉬운 문제였을 거 같지만, 대칭이 안되기 때문에 생각을 좀 했어야 했다. 이것저것 생각을 하다 마땅히 떠오르는게 없어서 풀이를 찾아보다가 이런걸 발견했다. 즉 이 문제에서 구할 것은 타일을 놓을 수 있는 전체 경우의 수에서 대칭되는 경우의 수를 빼면 된다는 것이다. 더욱 구체적으로 말하면, 2*n크기의 직사각형을 채우는 비대칭 타일링 방법의 수는 n번째 피보나치 수, 즉 타일링이 가능한 전체 수에서 n이 홀수일 때는 (n-1)/2 번째의 피보나치 수를 빼고, n이 짝수일 때는 (n+2)/2 번째의 피보나..

알고스팟 maxsum 문제 파이썬으로 풀기

문제는 주어진 정수 배열에서 가장 큰 부분합을 구하는 것이다. 문제를 처음 봤을 땐 0보다 작은 수의 위치를 구해 양수 및 0이 있는 배열만을 뽑아 그 중 최대치를 구하면 될 거 같다는 생각이 들었다. 그런데 예를 들어 -1 99 -1 99 이런식으로 배열이 주어졌을 때 최대의 부분합은 99 -1 99를 더한 197이다. 하지만 내가 생각한 것으로 구하면 99가 최대라고 계산하게 된다. 이렇게 음수를 포함하는 것도 가장 큰 부분합을 구하는데 영향을 줄 수 있어서 고민하다가 이 글을 보고 이대로 코드를 짜보기로 했다. 출력도 잘 이루어진다. 제출해보니 시간이 엄청 걸리긴 했지만 정답이 떳다. 느낀점: 1. 양수만 합하는 변수와 다 합하는 변수를 같이 이용해 거기서 최댓값을 구한 것처럼 문제를 구할 때 하나..