2019/02/13 - [Algorithm/Python] - [Programmers]Lv 1. 체육복


이전에 풀었던 문제인데 2.28일 이후로 테스트케이스가 추가되면서 하나의 케이스가 통과하지 못한다.

이전에는 조금 명시적으로 여분을 가지고 있는 학생이 구분이 되지 않았는데 더 명시적으로 여분을 가지고 있는 사람에게만 빌리게 하였더니 통과를 하였다.


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
def solution(n,lost,reserve):
    cloth=[1]*n
    for i in range(n):
        if i+1 in reserve:
            cloth[i]=2
        if i+1 in lost:
            cloth[i]-=1
    if cloth[0]==0:
        if cloth[1]==2:
            cloth[0]+=1
            cloth[1]-=1
    for i in range(1,n-1):
        if cloth[i]==0:
            if cloth[i+1]==2:
                cloth[i]+=1
                cloth[i+1]-=1
            elif cloth[i-1]==2:
                cloth[i]+=1
                cloth[i-1]-=1
    if cloth[-1]==0:
        if cloth[-2]==2:
            cloth[-1]+=1
            cloth[-2]-=1
    count=0
    for i in cloth:
        if i != 0:
            count+=1
    return count
cs

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

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

[Programmers]Lv 2.다음 큰 숫자  (0) 2019.03.06
[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04
[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01

문제:

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어 

수신 탑(높이) 

I 숫자 

큐에 주어진 숫자를 삽입합니다. 

D 1 

큐에서 최댓값을 삭제합니다. 

D -1 

큐에서 최솟값을 삭제합니다. 


이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값,최솟값]을 return 하도록 solution 함수를 구현해주세요.

풀이 방법:

힙을 사용해서 풀어야 하는 문제지만 굳이 힙을 사용해서 풀지 않아도 상관 없다. operations를 반복문의 매개변수로 받아 각 원소들을 공백으로 구분해보아서 명령어대로 배열에서 처리를 하면 문제없이 풀 수 있다. 삽입을 할 때 정수형으로 변경을 해서 넣는데 그 이유는 음수값들도 들어가기 때문에 정렬을 하기 위해서는 정수형으로 바꾸는 것이 필수적이기 때문이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(operations):
    answer=[]
    for i in operations:
        a,b=i.split(" ")
        if a=="I":
            answer.append(int(b))
        else:
            if len(answer)>0:
                if b=="1":
                    answer.pop()
                else:
                    answer.pop(0)
            else:
                pass
        answer.sort()
    if len(answer)==0:
        return [0,0]
    else:
        return [max(answer),min(answer)]
cs

만약 힙을 사용해서 풀고 싶다면 다음과 같이 하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq
def solution(operations):
    h=[]
    for i in operations:
        a,b=i.split(" ")
        if a=="I":
            heapq.heappush(h,int(b))
        else:
            if len(h)>0:
                if b=="1":
                    h.pop(h.index(heapq.nlargest(1,h)[0]))
                else:
                    heapq.heappop(h)
            else:
                pass
    if len(h)==0:
        return [0,0]
    else:
        return [heapq.nlargest(1,h)[0],heapq.nsmallest(1,h)[0]]
cs


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

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

[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04
[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28

문제:

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

2019/02/25 - [Algorithm/Python] - [Programmers]:Lv 3. 예산

문제:

n 명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그 곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

이분탐색 문제이므로 이 문제도 예산 문제와 같이 심사를 다 받는 시간을 찍어보면 된다. 왼쪽 값을 0 우측 값을 times의 가장 큰 값에 n을 곱한 값으로 설정하고 이분 탐색을 진행해 나가면 된다. 중간에 n명을 통과를 할 수 있는 시간이 있더라도 최소값을 찾기 위해 끝까지 진행해본다.
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(n, times):
    left=0
    right=max(times)*n
    temp=right
    answer=right
    while(right>=left):
        mid=(right+left)//2
        people=0
        for i in times:
            people+=mid//i
        if people==n:
            if answer>=mid:
                answer=mid
            right=mid-1
        elif people>n:
            right=mid-1
        else:
            left=mid+1
    if answer==temp:
        return right+1
    else:
        return answer
cs


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

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

[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]Lv 2. 카펫  (0) 2019.02.26

문제:

 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1,1,1,1,1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1=3
+1-1+1+1+1=3
+1+1-1+1+1=3
+1+1+1-1+1=3
+1+1+1+1-1=3

 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟
넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

깊이/너비 우선 탐색(DFS/BFS)는 트리 구조를 만드는 것이 핵심이다. 이 문제에서 타겟 넘버를 만드는 방법은 더하거나 빼거나 둘 중 하나다. 따라서 하나의 숫자에 대해 다음 값을 더하는 경우, 빼는 경우로 트리 구조를 만들어 나갈 수 있는 것이다. 첫 수부터 빼는 경우가 있을 수 있으므로 미리 0을 담아 놓고 시작 하도록 한다. 이후 트리를 다 완성 시킨 후 타겟 넘버인 target의 갯수를 카운트 하면 된다.


1
2
3
4
5
6
7
8
9
10
def solution(numbers, target):
    answer_list=[0]
    for i in numbers:
        temporary_list=[]
        for j in answer_list:
            temporary_list.append(j+i)
            temporary_list.append(j-i)
        answer_list=temporary_list
    answer = answer_list.count(target)
    return answer
cs


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

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

[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]:Lv 3. 예산  (0) 2019.02.25

문제:


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

문제:

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 모서리는 갈색으로 칠해져 있는 격자 모양 카펫을 봤씁니다.


Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.


Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로,세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.


풀이 방법:

이 카펫은 내부에 있는 빨간색의 모양에 따라서 갈색으로 칠한 수가 정해지게 된다. 이 문제가 완전탐색이므로 빨간색의 갯수로 나올수 있는 경우의 수를 모두 구해서 알맞은 경우를 찾도록 한다.
안의 빨간색의 모양은 사각형의 모양이므로 red의 약수마다 갈색의 갯수를 구한다. 이때 brown과 같아진다면 그 경우가 답이 되는 것이다.

1
2
3
4
5
6
7
8
9
10
def solution(brown, red):
    answer=[]
    for i in range(1,int(red/2)+2):
        if red%i==0:
            a,b=max(red//i,i),min(red//i,i)
            if 2*a+(b+2)*2==brown:
                answer.append(a+2)
                answer.append(b+2)
                break
    return answer
cs


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

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

[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]:Lv 3. 예산  (0) 2019.02.25
[Programmers]Lv 2. 구명 보트  (0) 2019.02.24
[Programmers]Lv 3.타일 장식물  (0) 2019.02.23

문제:

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다.
   상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120,110,140,150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120,110,127,127을 배정하고 그 합이 484로 가능한 최대가 됩니다.
각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때, 위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

이 문제는 처음 봤을 때, 예시를 보면 120~150 사이의 수를 모두 넣어보아서 최대가 되는 상한액을 찾으면 되는 것이 아닌가 라고 생각 할 수 있지만 그렇게 푼다면 아마 시간초과가 발생할 것이다.(총 예산이 1,000,000,000 이하인 수이다..)
따라서 이 문제의 태그가 이분탐색인 만큼 이분탐색을 사용해야 시간초과가 발생하지 않고 풀 수 있다. 이분탐색의 문제의 핵심은 '찍기'라고 생각하면 된다. 이 문제의 예시로 예를 들어보면 0~150의 수를 이분탐색의 방법으로 찍어가면서 최대 상한액을 찾아나가는 것이다.

처음에는 75를 상한액으로 고를 수 있고 75*4<=485이므로 왼쪽 값을 75+1로 선택하여 이분탐색을 진행한다.
그 다음엔 113을 상한액으로 고를 수 있고 이 역시 113*3+110<=485이므로 왼쪽값을 113+1로 선택하여 이분탐색을 진행한다.
그 다음엔 132를 상한액으로 고를 수 있고 120+110+132*2>=485이므로 오른쪽 값을 132-1로 선택하여 이분탐색을 진행한다.
이와 같이 계속 반복하다보면 127이 상한액일 때 최대가 됨을 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(budgets, M):
    left=0
    right=max(budgets)
    temp=0
    answer=0
    while(right>=left):
        mid=(left+right)//2
        result=0
        for i in budgets:
            if mid>i:
                result+=i
            else:
                result+=mid
        if result>M:
            right=mid-1
        else:
            if result>=temp:
                answer=mid
            left=mid+1
    return answer
cs


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

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

[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]Lv 2. 구명 보트  (0) 2019.02.24
[Programmers]Lv 3.타일 장식물  (0) 2019.02.23
[Programmers]Lv 2. 숫자 야구  (0) 2019.02.22

문제:

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

구명보트는 작아서 한 번에 최대 2명만 탈 수 있다는 점이 가장 중요하다. 또한 탐욕적 방법으로 해결해야 하므로 사람들의 몸무게를 정렬하고 가장 몸무게가 작은 사람과 무거운 사람과 매칭을 해보는 방법으로 진행을 해보았다. 만약 가장 작은 사람의 무게와 무거운 사람의 무게가 limit보다 작다면 탑승할 수 있는 것 이므로 count를 하나 늘리고 light의 인덱스를 1증가, heavy의 인덱스를 1감소 시킨다. 만약 limit보다 크다면 heavy의 인덱스만 1감소 시킨다.
이를 light의 인덱스가 heavy의 인덱스를 앞지를 때까지 반복한다.
이후 최종 구명보트의 수는 people의 전체 길이에서 count 값을 뺀 값이 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(people,limit):
    people.sort()
    length=len(people)
    light=0
    heavy=length-1
    count=0
    while(light<heavy):
        if people[light]+people[heavy]<=limit:
            count+=1
            light+=1
            heavy-=1
        else:
            heavy-=1
    return length-count
cs


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

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

[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]:Lv 3. 예산  (0) 2019.02.25
[Programmers]Lv 3.타일 장식물  (0) 2019.02.23
[Programmers]Lv 2. 숫자 야구  (0) 2019.02.22
[Programmers]Lv 3. 2 X N 타일링  (0) 2019.02.21

문제:

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 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

+ Recent posts

티스토리툴바