'프로그래머스' 태그의 글 목록 (10 Page)

문제:

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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])
Colored by Color Scripter
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

문제:

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다

조건 2. n의 다음 큰 숫자는 n은 2진수로 변환했을 때 1의 갯수가 같습니다.

조건 3. n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

풀이 방법:

우선 자연수 n의 이진수 값을 구하기 위해서 내장함수인 bin을 사용하였다. bin은 십진수의 값을 이진수로 변환해주는 함수다. 단 이진수 앞 부분에 '0x' 가 붙으며 문자열로 반환을 한다. 하지만 문제에선 1의 갯만 필요하므로 상관 없이 1의 갯수를 세주도록 한다.

이 후 다음 큰 숫자를 찾기 위해서 n부터 1씩 증가하며 n의 1의 갯수와 같을 때까지 계속 반복하면 된다.

1
2
3
4
5
6
7
8
9
10
11
def solution(n):
    answer=n
    n_count=bin(n).count('1')
    conti=True
    while conti:
        answer+=1
        temp=answer
        n_next_count=bin(temp).count('1')
        if n_count == n_next_count:
            break     
    return answer
cs

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

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

[Programmers]Lv 2.땅따먹기 (0)	2019.03.08
[Programmers] Lv 3. 등굣길 (2)	2019.03.07
[Programmers]Lv 2.올바른 괄호 (0)	2019.03.04
[Programmers]Lv 1. 체육복(테스트케이스 수정) (0)	2019.03.03
[Programmers]Lv 3. 이중우선순위큐 (1)	2019.03.03

문제:

올바른 괄호란 두 개의 괄호 '(' 와 ')' 만으로 구성되어 있고, 괄호가 올바르게 짝지어진 문자열입니다. 괄호가 올바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 합니다.

예를 들어

"()()" 또는 "(())()"는 올바른 괄호입니다.

")()(" 또는 "(()("는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return하는 solution 함수를 완성해주세요.

풀이 방법:

'(' 는 +1의 값을 가지고 ')'이 -1의 값을 가진다고 하자.

모두 정상적으로 짝을 이뤘다. 즉 "(" 와 ")"의 갯수가 동일하다면 문자열 s를 반복문으로 한 번씩 탐색해보았을 때 count의 값이0이 되어야 할 것이다.

만약 count의 값이 양수가 나온다면 "("가 더 있는 것이고 음수면 그 반대일 것이다.

하지만 괄호의 갯수는 맞게 이루어져있지만 반대로 있을 수도 있다. (ex ")(" )

이와 같은 경우에는 문자열의 합은 0이 나오지만 올바르지 않은 괄호이다. 따라서 조건을 하나 더 추가를 해줘야 한다.

문제가 발생 할 때에는 ")"에서 나오게 된다. "("로 열지도 않았는데 ")"로 닫아버릴 때 오류가 발생한다. 즉 count값이 순간적으로 마이너스가 될 경우가 오류가 발생하게 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(s):
    count=0
    for i in s:
        if i is '(':
            count+=1
        elif i is ')':
            count-=1
            if count < 0 :
                return False
    if count == 0:
        return True
    else:
        return False
cs

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

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

[Programmers] Lv 3. 등굣길 (2)	2019.03.07
[Programmers]Lv 2.다음 큰 숫자 (0)	2019.03.06
[Programmers]Lv 1. 체육복(테스트케이스 수정) (0)	2019.03.03
[Programmers]Lv 3. 이중우선순위큐 (1)	2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기 (0)	2019.03.02

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
Colored by Color Scripter
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])
Colored by Color Scripter
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