문제:

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

전설카드
레드카드
오렌지카드
퍼플카드
블루카드
청록카드
그린카드
그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다. 

예를 들어, 카드팩이 총 4가지 종류가 있고, P1=1, P2=5, P3=6, P4=7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

마지막으로, P1=3, P2=5, P3=15, P4=16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력:

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다.(1<=N,<=1,000)
둘때 줄에는 Pi가 P1부터 Pn까지 순서대로 주어진다.(1<=Pi<=10,000)

출력:

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

풀이 방법:

동적계획법을 사용해서 문제를 풀었다. N개를 갖기 위해 지불해야 하는 금액을 구하기 위해서 N-1개까지 지불해야하는 금액을 모두 구했다. 이를 통해 N개를 갖기 위해 지불해야 하는 최댓값을 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
dps=[]
number=int(input())
num_list=list(map(int,input().split()))
for i in range(number+1):
    dps.append([])
    for j in range(number+1):
        if i==j:
            dps[i].append(num_list[i-1])
        else:
            dps[i].append(0)
for i in range(2,len(dps)):
    for j in range(1,i):
        dps[i][j]=num_list[j-1]+max(dps[i-j][:i-j+1])
print(max(dps[-1]))
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]9461.파도반 수열  (0) 2019.04.25
[BOJ]9095. 1,2,3 더하기  (0) 2019.04.24
[BOJ]10844. 쉬운 계단 수  (0) 2019.04.22
[BOJ]1149. RGB거리  (0) 2019.04.21
[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20

문제:

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질
때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력:

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력:

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이 방법:

길이가 하나 길어질수록 그 전의 길이에 영향을 받는다. 임의의 숫자 n에 대해서 생겨지는 계단 수의 수는 이전의 n-1 과 n+1의 수의 합이다. 하지만 끝값 0이나 9와 같은 경우에는 계단수를 유지하기 위해 각각 1과 8만 와야 하므로 이 경우에 대해서만 더해주도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
dp=[]
for i in range(int(input())+1):
    dp.append([])
    for j in range(10):
        if i==1:
            dp[i].append(1)
        else:
            dp[i].append(0)
for i in range(2,len(dp)):
    for j in range(10):
        if j==0:
            dp[i][j]+=dp[i-1][j+1]%1000000000
        elif j==9:
            dp[i][j]+=dp[i-1][j-1]%1000000000
        else:
            dp[i][j]+=dp[i-1][j-1]+dp[i-1][j+1]%1000000000
print(sum(dp[-1][1:])%1000000000)
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]9095. 1,2,3 더하기  (0) 2019.04.24
[BOJ]11052. 카드 구매하기  (0) 2019.04.23
[BOJ]1149. RGB거리  (0) 2019.04.21
[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20
[BOJ]1912. 연속합  (0) 2019.04.19

문제:

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.

풀이 방법:

우선 입력으로 들어온 값들을 이차원 배열꼴로 만들어준다. 그리고 난 뒤 0번째 행부터가 아닌 1번째 행부터 각 원소에 대해 전 행에서 자신의 열과 다른 값들중 최솟값을 더해준다. 이를 계속 누적해서 끝 행까지 반복하고 최종적으론 끝 행의 최솟값을 반환하도록 한다.

1
2
3
4
5
6
7
8
9
10
array=[]
for i in range(int(input())):
    array.append([])
    houses=map(int,input().split())
    for house in houses:
        array[i].append(house)
for i in range(1,len(array)):
    for j in range(len(array[i])): 
        array[i][j]+=min(array[i-1][:j]+array[i-1][j+1:])
print(min(array[-1]))
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]11052. 카드 구매하기  (0) 2019.04.23
[BOJ]10844. 쉬운 계단 수  (0) 2019.04.22
[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20
[BOJ]1912. 연속합  (0) 2019.04.19
[BOJ]2504. 괄호의 값  (0) 2019.04.18

문제:

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12 + 21 인 33이 된다.

입력:

첫째 줄에 정수 n(1<=n<=100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.


출력:

첫째 줄에 답을 출력한다.


풀이 방법:

DP를 활용해서 푸는 문제이다. 반복문은 여러개 써야 할 것 같지만 배열 한 번을 탐색하는 반복문 하나로도 풀 수 있다. 정답을 maxsum이라 하고 초기값을 -1000으로 잡아준다. 왜냐하면 모든 수는 -1,000보다는 크기 때문이다. 배열중 임의의 값과 그 전부터 누적해온 값 중 더 큰 값을 선택하고 이를 maxsum과 비교해서 maxsum보다 커지는 값들이 있다면 그 값을 maxsum으로 갱신해준다.

예시 케이스로 설명하면 다음과 같이 된다.
처음에는 max(10,0+10)이므로 temp가 10이 되고 maxsum은 당연히 10으로 최신화된다.
그 다음에는 max(-4,10-4)이므로 temp가 6이 되지만 maxsum은 유지된다.
max(3,6+3)이므로 temp가 9가 되지만 maxsum은 유지된다.
max(1,9+1)이므로 temp가 10이 되지만 maxsum은 유지된다.
max(6,10+6)이므로 temp가 16이 되고 maxsum이 16이 된다.
max(-35,16-35)이므로 temp가 -19가 되고 maxsum은 유지된다.
max(12,-19+12)이므로 temp가 12가 되고 maxsum은 유지된다.
max(21,12+21)이므로 temp가 33이 되고 maxsum은 갱신된다.
max(-1,33-1)이므로 temp가 32가 되고 maxsum은 유지된다.

따라서 12+21인 33이 정답이 된다.

1
2
3
4
5
6
7
8
9
n=int(input())
arr=list(map(int,input().split()))
temp=0
maxsum=-1000
for num in arr:
    temp=max(num,temp+num)
    if temp>maxsum:
        maxsum=temp
print(maxsum)
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1149. RGB거리  (0) 2019.04.21
[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20
[BOJ]2504. 괄호의 값  (0) 2019.04.18
[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]1874. 스택 수열  (0) 2019.04.16

문제:

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면

|1|2|3|5|

|5|6|7|8|

|4|3|2|1|

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸(8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7),3행의 첫번째 칸(4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

풀이 방법:

이 문제도 동적계획법을 사용해서 풀 수 있다. 맨 위의 행부터 시작해서 아래로 진행을 하면서 행의 값들을 바꾸어 주면 된다. 행의 값들을 업데이트 할 때 같은 열을 연속해서 밟지는 못하므로 현재 열을 제외하고 이전 행에서 현재 열을 제외한 최댓값을 찾아서 현재 형,열에 값을 더해주면 된다. 이를 맨 밑의 행까지 계속해서 반복을 한다.

즉 예시는 다음과 같이 바뀔 수 있다.

|1|2|3|5|                       |1|2|3|5|                       |1|2|3|5|

|5|6|7|8|            -->      |10|11|12|11|         -->   |10|11|12|11|  

|4|3|2|1|                       |4|3|2|1|                       |16|15|13|13|

1
2
3
4
5
def solution(land):
    for i in range(1,len(land)):
        for j in range(len(land[0])):
            land[i][j]=land[i][j]+max(land[i-1][:j]+land[i-1][j+1:])
    return max(land[-1])
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.폰켓몬  (0) 2019.03.10
[Programmers]Lv 3.베스트앨범  (0) 2019.03.09
[Programmers] Lv 3. 등굣길  (2) 2019.03.07
[Programmers]Lv 2.다음 큰 숫자  (0) 2019.03.06
[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04

문제:

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1,1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m,n)으로 나타냅니다. 격자의 크기 m,n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어질 때, 학교에서 집에서 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

동적계획법을 사용하는 문제이므로 왼쪽 위 집에서 부터 하나씩 모든 경우의 수를 계산하며 학교를 가면 되는 문제이다.
예시로 (2,3)으로 가는 방법은 왼쪽에서 오는 방법과 위에서 오는 방법이 있다. 왜냐하면 최단 경로로 가기 위해서는 (1,1)에서 오른쪽이나 아래로만 움직여야 하기 때문이다. 따라서 (2,3)으로 오는 방법은 (1,3) 혹은 (2,2)에서 출발 해야 하는 것이다. 하지만 이 문제에선 물에 잠긴 지역이 있다면 아예 이동을 할  수 없으므로 puddles에 있는 원소 값들은 항상 0의 값을 가지도록 하면 된다.

이 문제의 예시로 표를 만들면 다음과 같이 만들어 진다.

 

 0

0 

0 

0 

0 

 1(집)

1 

1 

1 

0 

1 

0(물 웅덩이) 

1 

2 

0 

1 

1

2 

4(학교) 




계산의 용이성을 위해서 m,n 칸의 표가 아닌 m+1,n+1 칸의 0 행렬을 만들었다. 또한 우리가 알고 있는 좌표 평면과 표에서 그려지는 좌표가 반대로 구성되어 있음을 알 수 있다. 따라서 puddles에 있는지 확인 하기 위해선 i,j 의 위치를 바꾸어서 확인을 해야한다.

1
2
3
4
5
6
7
8
9
10
11
12
def solution(m, n, puddles):
    answers=[[0]*(m+1) for i in range(n+1)]
    answers[1][1]=1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if i==1 and j==1:
                continue
            if [j,i] in puddles:
                answers[i][j]=0
            else:
                answers[i][j]=answers[i-1][j]+answers[i][j-1]
    return answers[n][m]%1000000007
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3.베스트앨범  (0) 2019.03.09
[Programmers]Lv 2.땅따먹기  (0) 2019.03.08
[Programmers]Lv 2.다음 큰 숫자  (0) 2019.03.06
[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04
[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03

문제:

1과 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요.( 단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

풀이 방법:

이 문제는 DP(dynamic programming), 동적계획법을 사용해서 풀어야 하는 문제이다. 왼쪽 위(1,1)부터 시작해서 오른쪽 아래로 진행을 하면서 정사각형을 나간다. 

정사각형으로 취급되는 경우는 다음과 같다.


1(1번)

1(2번) 

 1(3번) 

1(4번) 


4번의 값이 0이 아니라면 1,2,3번의 값을 비교해 최소값을 찾은 뒤에 4번 자리에 그 최솟값에 1을 더한 값을 넣어 준다. 즉 다음과 같이 된다.


1(1번)

1(2번) 

 1(3번) 

2(4번) 


최솟값을 찾는 이유는 하나의 0이 있다면 정사각형의 형태가 아니므로 1 이상의 값들만 이어나가기 위함이다. 또한 1을 더해주는 이유는 정사각형이라면 길이의 값을 누적하기 위해서이고 아니라면 남은 1의 값들이 다른 곳에서 정사각형을 이룰 수 있기 때문에 이어나가주는 것이다.

이 문제의 예시를 통해서 구하는 방법을 알아보자. 다음과 같이 처음 상태가 있다.


0 

1 

1 

1

1 

1 

1 

1

1 

1 

1

1

0

0

1

0


처음 왼쪽 위 (1,1)을 비교해 보았을 때 (0,0)이 0이기에 (1,1)의 값을 1로 바꾼다.


0 

1 

1 

1

1 

1 

1 

1

1 

1 

1

1

0

0

1

0


(1,2)의 값을 비교해 보았을 때  주위 최솟값이 1이므로 (1,2)의 값을 2로 바꾼다. 이 경우가 길이가 2인 정사각형을 찾은 경우이다. 하지만 가장 큰 정사각형을 찾는 것이 문제이므로 계속 탐색해보도록 한다.

0 

1 

1 

1

1 

1 

2

1

1 

1 

1

1

0

0

1

0


(1,3)의 값을 비교해보았을 때, 주위 최솟값이 1이므로 (1,3)의 값을 2로 바꾼다. 이 경우도 역시 길이가 2인 정사각형을 찾은 경우다. 이전 (1,2)에서도 정사각형을 찾았지만 이 둘로는 정사각형이 아닌 직사각형이 만들어지므로 서로 영향을 주진 못한다.

0 

1 

1 

1

1 

1 

2 

2

1 

1 

1

1

0

0

1

0


계속해서 이 방법대로 진행을 하면 (2,2)까지 다음과 같이 표를 바꿀 수 있다.

0 

1 

1 

1

1 

1 

2 

2

1 

2 

2

1

0

0

1

0


(2,3)에서는 주위의 최솟값이 2이므로 (2,3)의 값을 3으로 바꾼다 즉 길이가 3인 정사각형을 찾은 경우다. 이 처럼 주위의 값들이 모두 2,2,2 혹은 3,3,3 과 같이 이루어져 있을 경우에 가장 큰 정사각형의 길이가 바뀌게 되는 것이다.

0 

1 

1 

1

1 

1 

2 

2

1 

2 

2

3

0

0

1

0


마지막 줄은 계속 진행해보아도 변경되는 점이 없으므로 이 예시의 가장 큰 정사각형은 길이가 3인 정사각형이다.

다른 채점케이스에서 전부다 0인 경우에는 위와 같은 방법으로 길이가 1인 정사각형이 있다고 나오므로 따로 구분해서 구하도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(board):
    max_point=0
    for i in range(len(board)):
        max_point+=sum(board[i][:])
    if max_point==0:
        return 0
    max_point=0
    for i in range(1,len(board)):
        for j in range(1,len(board[0])):
            if board[i][j]==0:
                continue
            else:
                min_point=min(board[i][j-1],board[i-1][j],board[i-1][j-1])
                min_point+=1
                board[i][j]=min_point
                if max_point < board[i][j]:
                    max_point=board[i][j]
    if max_point==0:
        return 1
    else:
        return max_point**2
cs




저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03
[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27

문제:


위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중,거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.


삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.


풀이 방법:

동적계획법 문제임을 이용해서 꼭대기에서 부터 업데이트 해가면서 풀어야 하는 문제이다. 한 칸을 업데이트를 할 경우에는 크게 두 가지가 경우가 있다.

1. 양쪽 끝일 때


양쪽 끝의 숫자들은 다음과 같이 그 전 칸의 처음 혹은 끝의 영향만을 받는다. 따라서 별도의 비교 없이 업데이트 해가면 된다.


2. 그 외의 경우



가운데에 있는 숫자들은 두 개의 숫자를 비교를 해야 한다. 가장 큰 경우를 구해야 하므로 둘 중 큰 경우를 선택해서 더해주면 된다.


위의 규칙을 따라서 다음과 같은 순서로 진행이 된다.


       7

      3 8

     8 1 0

    2 7 4 4

   4 5 2 6 5


예시와 같이 이러한 삼각형이 있다고 하면 처음에는 양쪽 끝에만 영향을 주는 경우 이므로 7을 각각 더해준다.


        7

     10 15

    8  1  0

   2  7  4  4

  4 5  2  6  5


8과 0의 경우에는 1번 경우이므로 10과 15를 각각 더해주면 되고 1은 10과 15중 15가 더 크므로 15를 더해 주도록 한다.


        7

     10 15

   18 16 15

   2   7  4   4

 4   5   2  6  5


2와 맨 끝의 4의 경우엔 1번이므로 18과 15를 각각 더해주고 7은 18과 16 중 18이 더 크므로 18을 더하고 4는 16과 15 중 16이 더 크므로 16을 더한다.


        7

     10 15

   18 16 15

  20 25 20 19

 4   5  2   6   5


위와 같은 방법으로 계속 더해가면 된다.


        7

     10 15

   18 16 15

  20 25 20 19

24 30 27 26 24


이후 맨 마지막 인덱스 배열의 최댓값을 구하면 30을 얻을 수 있다.


1
2
3
4
5
6
7
8
9
10
def solution(triangle):
    for i in range(1,len(triangle)):
        for j in range(i+1):
            if j==0:
                triangle[i][j]+=triangle[i-1][j]
            elif j==i:
                triangle[i][j]+=triangle[i-1][j-1]
            else:
                triangle[i][j]+=max(triangle[i-1][j],triangle[i-1][j-1])
    return max(triangle[-1])
cs



저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]:Lv 3. 예산  (0) 2019.02.25
[Programmers]Lv 2. 구명 보트  (0) 2019.02.24

문제:

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.


 

 그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다..


[1,1,2,3,5,8,...]


 지수는 문들 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.


타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.


풀이 방법:

다음 직사각형의 한 변의 길이는 이전의 두 개의 직사각형 한 변의 길이 합으로 만들어진다. 이 말은 직사각형의 길이가 피보나치 수열을 따른 다는 것이다. 따라서 피보나치 수열을 이용해서 직사각형의 변의 길이를 구한 뒤에 둘레를 구해주면 된다.

1
2
3
4
5
6
7
def solution(N):
    a,b=1,1
    while(N>1):
        a,b=b,a+b
        N-=1
    answer=a*2+b*2
    return answer
cs



저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]:Lv 3. 예산  (0) 2019.02.25
[Programmers]Lv 2. 구명 보트  (0) 2019.02.24
[Programmers]Lv 2. 숫자 야구  (0) 2019.02.22
[Programmers]Lv 3. 2 X N 타일링  (0) 2019.02.21
[Programmers]Lv 2. 위장  (0) 2019.02.20

문제:

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 +(5/5) +(5/5)
12 = 55/5 + 5/5
12 = (55 + 5)/5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

풀이 방법:

이 문제는 절대로 1단계에 있을 문제라고 생각이 들지 않는다.

숫자를 표현하는 방법에는 총 5가지가 있다.

1. 더하기 2. 곱하기 3. 빼기 4.나누기 5. 숫자 붙이기

따라서 위 방법에 따라 숫자를 생성하는 generator(N,n) 이라는 함수를 만들었다. 이 함수는 숫자 N과 그 숫자를 사용할 횟수 n이 주어지면 N을 n개 사용해서 생기는 모든 경우를 반환해준다.
DP(동적계획법)을 사용하는 문제임을 인지하고 풀었다. 최솟값이 8보다 크면 -1을 반환하기에 경우의 수가 엄청 많지는 않다.
예를 들어 N을 4번 사용해서 number를 만들 수 있다고 하자. generator(N,4) 는 generator(N,3)에다가 N을 하나씩 더 연산해준 것이다. 즉 3+1=4 연산을 했다. 하지만 2+2=4 인 경우도 있다. 하지만 내가 고안한 generator로는 2+2를 바로 얻을 수 없기 때문에 generator(N,2) 2개를 활용해 얻도록 하였다.
또한 작은 경우에서부터 시작하므로 answer의 min 값보다 큰 경우를 시행하는 경우에는 break로 바로 빠져 나오도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def generator(N,n):
    answer = [N]
    if n==1:
        return answer
    for i in range(2,n+1):
        temporary=[]
        for j in answer:
            temporary.append(j+N)
            if abs(j-N)!=0:
                temporary.append(abs(j-N))
            a,b=max(j,N),min(j,N)
            temporary.append(a//b)
            temporary.append(j*N)
        answer+=temporary
        answer.append(int(str(N)*i))
    return answer
 
def solution(N, number):
    answer= [9]
    if N==number:
        return 1
    for i in range(1,8):
        if number in generator(N,i):
            answer.append(i)
    for i in range(2,5):
        answer1=generator(N,i)
        for j in range(i,9-i):
            answer2=generator(N,j)
            if min(answer)<i+j:
                pass
            else:
                temporary=[]
                for l in answer2:
                    for k in answer1:
                        temporary.append(k+l)
                        temporary.append(abs(k-l))
                        c,d=max(l,k),min(l,k)
                        if d!=0:
                            temporary.append(c//d)
                        temporary.append(l*k)
                if number in temporary:
                    answer.append(i+j)
    if answer==[9]:
        return -1
    else:
        return min(answer)
        return min(answer)
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 2 X N 타일링  (0) 2019.02.21
[Programmers]Lv 2. 위장  (0) 2019.02.20
[Programmers]Lv 2. H-Index  (0) 2019.02.18
[Programmers]Lv 2.전화번호 목록  (0) 2019.02.16
[Programmers]Lv 1.모의고사  (0) 2019.02.15

+ Recent posts

티스토리툴바