동적계획법4 [프로그래머스] 2 x n 타일링 문제설명 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 해결 방법 동적 계획법(DP, Dynamic Programming)을 활용해 해결할 수 있는 문제. 가로의 길이가 n일 때 나올 수 있는 경우의 수를 D[n]이라 할 때, 아래와 같이 경우의 수가 나오게 된다... 2020. 3. 23. [프로그래머스] 정수 삼각형 문제설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 해결 방법 동적계획법(DP, Dynamic Programming)으로 해결할 수 있는 문제로, 문제에서 1번째 층에서 n번째 층으로 갔을 때, 합의 최댓값을 구하라고 했다. 이 말은 i층에서 i+1층으로 갈 때 갈 수 있는 두 값중 큰 값을 거쳐야한다는 말과 같다. 즉, i층은 i+1.. 2020. 3. 22. [프로그래머스] 타일 장식물 문제설명 문제 설명 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다. 그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. [1, 1, 2, 3, 5, 8, .] 지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다. 타일의 개수 N이 주어질.. 2020. 3. 22. [SWEA] 8659. GCD 문제 의석이는 종강 기념 피자 파티를 열기 위해서 피자를 사러 왔다. 하지만 피자 가게 주인 동욱이는 피자를 순순히 판매하지 않는 사람이다. 돈 보다 문제 내는 것을 더 좋아하는 이상한 동욱이는 피자를 사러 온 의석이에게 3개의 시련을 부여했고, 모두 통과해야만 거래를 시작한다. 두 번째 관문에서는 GCD에 관련된 내용을 물어본다. GCD(a,0) = a GCD(a,b) = GCD(b, a%b) GCD는 위와 같은 성질을 가진 함수이다. 동욱이가 원하는 것은 두 개의 숫자 A, B(A>B)를 찾는 것이다. 단, 이 두 개의 숫자에 대해서 GCD(A,B)를 실행하면 % 연산자가 총 K 번 수행된다는 사실을 알고 있다. 이러한 두 개의 숫자 조합 중에서 A가 가장 작으며 그런 조합이 여러 가지라면 B가 가장.. 2020. 3. 10. 이전 1 다음
