728x90
반응형

문제:

길이가 같은 배열 A,B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A,B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A=[1,4,2], B=[5,4,4] 라면

* A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값: 0 + 5(1x5) = 5)
* A에서 두번째 숫자인 4, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값: 5 + 16(4x4) = 21)
* A에서 세번째 숫자인 2, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값: 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A,B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해주세요.

풀이 방법:

 최소값을 만들기 위해서는 A에서 작은 값을 선택하면 B에서 가장 큰 값을 골라서 곱하는 방식으로 누적하는 것이 가장 최소가 된다.

1
2
3
4
5
6
7
def solution(A,B):
    answer=0
    A.sort()
    B.sort(reverse=True)
    for i in range(len(A)):
        answer+=A[i]*B[i]
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2. 피보나치 수  (0) 2019.03.18
[Programmers]Lv 3.줄 서는 방법  (0) 2019.03.17
[Programmers]Lv 3. 야근 지수  (2) 2019.03.15
[Programmers]Lv 2. 최댓값과 최솟값  (0) 2019.03.14
[Programmers]Lv 3. 방문길이  (0) 2019.03.13
728x90
반응형

문제:

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겂니다. Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

풀이 방법:

야근 지수를 최소화하려면 일정 값들을 0으로 바꾸는 것보다 각 원소들을 가능한 작게 만드는 것이 더 도움이 된다. 즉 n만큼의 수를 감소시키는 것을 몇 개의 값들에 집중해서 하는 것이 아니라 골고루 사용해야 하는 것이다. 따라서 n번 works의 최댓값을 1씩 빼주는 작업을 하면 된다.

1
2
3
4
5
6
7
8
9
10
def solution(n, works):
    answer = 0
    if n > sum(works):
        return answer
    for i in range(n):
        works.sort()
        works[-1]-=1
    for i in works:
        answer+=i*i
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 3.줄 서는 방법  (0) 2019.03.17
[Programmers]Lv 2. 최솟값 만들기  (0) 2019.03.16
[Programmers]Lv 2. 최댓값과 최솟값  (0) 2019.03.14
[Programmers]Lv 3. 방문길이  (0) 2019.03.13
[Programmers]Lv 2.숫자의 표현  (0) 2019.03.12
728x90
반응형

문제:

문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 "(최소값) (최대값)"형태의 문자열을 반환하는 함수, solution을 완성하세요.
예를 들어 s가 "1 2 3 4"라면 "1 4"를 리턴하고, "-1 -2 -3 -4"라면 "-4 1"을 리턴하면 됩니다.

풀이 방법:

map과 split을 사용하면 쉽게 풀 수 있다. s를 공백을 기준으로 분할한 뒤 map을 사용해서 다 int로 바꾸고 그 중 min값과 max를 찾으면 된다.

1
2
3
4
def solution(s):
    s=list(map(int,s.split(" ")))
    answer = "{} {}".format(min(s),max(s))
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2. 최솟값 만들기  (0) 2019.03.16
[Programmers]Lv 3. 야근 지수  (2) 2019.03.15
[Programmers]Lv 3. 방문길이  (0) 2019.03.13
[Programmers]Lv 2.숫자의 표현  (0) 2019.03.12
[Programmers] Lv 3. 멀리 뛰기  (0) 2019.03.11
728x90
반응형

문제:

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

U: 위쪽으로 한 칸 가기
D: 아래쪽으로 한 칸 가기
R: 오른쪽으로 한 칸 가기
L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0,0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5,5), 왼쪽 아래(-5,-5), 오른쪽 위(5,5), 오른쪽 아래(5,-5)로 이루어져 있습니다.



예를 들어, "ULURRDLLU"로 명령했다면 1번 명령어부터 7번 명령어 까지 다음과 같이 움직입니다.



8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.



이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8,9 번 명령어에서 움직인 길은 2,3번 명령어에서 이미 거쳐 간 길입니다.)


단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.


예를 들어, "LULLLLLLU"로 명령했다면 1번 명령어부터 6번 명령어대로 움직인 후, 7,8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.



이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

풀이 방법:

기본적인 풀이 방법은 튜플값을 사용해 좌표를 나타냈다. 명령어대로 움직였을 때, 좌표평면 밖으로 나가거나 이미 중복된 길을 지나는 경우가 발생할 수 있다. 이를 방지하기 위해서 x_count, y_count 라는 x 좌표, y 좌표 값을 만들었고, answer_list를 만들어서 이미 지나간 경로인지 확인해보았다.
dirs에 따라서 좌표평면밖으로 나가는지 확인하고, 나가지 않았다면 이미 지나간 경로인지 파악을 하였다. 두 조건에 모두 해당하지 않았다면 answer_list에 담고 dirs를 끝낸 뒤엔 answer_list의 길이를 반환하였다.

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
def solution(dirs):
    answer_list=[]
    x_count=0
    y_count=0
    for i in dirs:
        if i=="U":
            if (y_count<5):
                y_count+=1
                if ((x_count,y_count-1),(x_count,y_count)) in answer_list:
                    pass
                else:
                    answer_list.append(((x_count,y_count-1),(x_count,y_count)))
        elif i=="D":
            if (y_count>-5):
                y_count-=1
                if ((x_count,y_count),(x_count,y_count+1)) in answer_list:
                    pass
                else:
                    answer_list.append(((x_count,y_count),(x_count,y_count+1)))
        elif i=="L":
            if (x_count>-5):
                x_count-=1
                if ((x_count,y_count),(x_count+1,y_count)) in answer_list:
                    pass
                else:
                    answer_list.append(((x_count,y_count),(x_count+1,y_count)))
        elif i=="R":
            if (x_count<5):
                x_count+=1
                if ((x_count-1,y_count),(x_count,y_count)) in answer_list:
                    pass
                else:
                    answer_list.append(((x_count-1,y_count),(x_count,y_count)))
    return len(answer_list)
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 3. 야근 지수  (2) 2019.03.15
[Programmers]Lv 2. 최댓값과 최솟값  (0) 2019.03.14
[Programmers]Lv 2.숫자의 표현  (0) 2019.03.12
[Programmers] Lv 3. 멀리 뛰기  (0) 2019.03.11
[Programmers]Lv 2.폰켓몬  (0) 2019.03.10
728x90
반응형

문제:

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를 들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1+2+3+4+5=15
4+5+6=15
7+8=15
15=15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

풀이 방법:

연속한 자연수들의 합으로 표현을 해야하기 때문에 자연수 n의 절반이 넘는 수는 사용할 수가 없다. 따라서 1부터 n//2+2 까지 반복문으로 돌려서 합이 n이 되는 경우들을 찾아주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(n):
    answer=0
    a=range(1,n//2+2)
    for i in a:
        s=0
        for j in range(i,n//2+2):
            s+=j
            if s==n:
                answer+=1
            elif s > n:
                break
    answer+=1
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2. 최댓값과 최솟값  (0) 2019.03.14
[Programmers]Lv 3. 방문길이  (0) 2019.03.13
[Programmers] Lv 3. 멀리 뛰기  (0) 2019.03.11
[Programmers]Lv 2.폰켓몬  (0) 2019.03.10
[Programmers]Lv 3.베스트앨범  (0) 2019.03.09
728x90
반응형

문제:

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는

(1칸,1칸,1칸,1칸)
(1칸,2칸,1칸)
(1칸,1칸,2칸)
(2칸,1칸,1칸)
(2칸,2칸)

의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리 뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면,5를 return하면 됩니다.

풀이 방법:

임의의 수 n이 주어졌다고 하자. 한번에 움직일 수 있는 칸은 1칸 혹은 2칸이기 때문에 n으로 이동하기 위해서는 n-2칸에서 2칸을 사용해서 n번째 칸으로 오거나 n-1에서 1칸을 이동해서 n칸으로 이동하는 방법이 있다. 재귀를 사용해서 풀어도 괜찮으나 피보나치 수열을 이루기 때문에 피보나치 수열을 이용해서 풀었다.

1
2
3
4
5
def solution(n):
    a,b =1,2
    for i in range(n-1):
        a,b=b,a+b
    return a%1234567
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 3. 방문길이  (0) 2019.03.13
[Programmers]Lv 2.숫자의 표현  (0) 2019.03.12
[Programmers]Lv 2.폰켓몬  (0) 2019.03.10
[Programmers]Lv 3.베스트앨범  (0) 2019.03.09
[Programmers]Lv 2.땅따먹기  (0) 2019.03.08
728x90
반응형

문제:

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번,1번,2번,3번]이라면 이는 3번 폰켓몬 두 마리,1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1.첫 번째(3번),두 번째(1번) 폰켓몬을 선택
2.첫 번째(3번),세 번째(2번) 폰켓몬을 선택
3.첫 번째(3번),네 번째(3번) 폰켓몬을 선택
4.두 번째(1번),세 번째(2번) 폰켓몬을 선택
5.두 번째(1번),네 번째(3번) 폰켓몬을 선택
6.세 번째(2번),네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2 마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이 방법:

이 문제는 크게 두 가지 경우가 있다. 폰켓몬의 종류의 갯수가 N/2마리보다 큰 경우와 작은 경우이다.
폰켓몬의 종류의 갯수가 N/2마리 보다 크다면 N/2마리를 선택하면 된다. 최대 선택할 수 있는 종류는 N/2이기 때문이다.
폰켓몬의 종류의 갯수가 N/2마리 보다 작다면 폰켓몬의 종류의 갯수를 선택하면 된다. 아무리 N/2마리를 골라도 중복이 발생하고 이를 제거 하면 결국 최댓값은 폰켓몬의 종류의 갯수가 되기 때문이다.
그렇다면 폰켓몬의 종류의 갯수를 구하는 것이 중요한데, python에서 중복을 제거 할 수 있는 가장 좋은 방법은 set을 이용하는 것이다. python의 자료형 중 집합 자료형인 set은 중복을 허용하지 않고, 정렬이 되어 있지 않다는 것이다. 따라서 nums를 set으로 한번 감싸고 난 뒤의 길이를 이용해서 N/2와 비교하면 된다.

1
2
3
4
5
def solution(num):
    if len(list(set(num))) < len(num)/2:
        return int(len(list(set(num))))
    else:
        return int(len(num)/2)
cs
 


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2.숫자의 표현  (0) 2019.03.12
[Programmers] Lv 3. 멀리 뛰기  (0) 2019.03.11
[Programmers]Lv 3.베스트앨범  (0) 2019.03.09
[Programmers]Lv 2.땅따먹기  (0) 2019.03.08
[Programmers] Lv 3. 등굣길  (2) 2019.03.07
728x90
반응형

문제:

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

풀이 방법:

 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays를 노래를 수록하는 기준에 따라서 해시로 구성해서 풀어야 하는 문제이다.


 우선 기준 1에 의해 속한 노래가 많이 재생된 장르를 먼저 수록해야 하므로 장르별로 재생된 횟수를 나타내는 해시인 sum_set을 만들어야 한다. 이와 동시에 기준 2 장르 내에서 많이 재생된 노래를 먼저 수록해야 하므로 장르를 key 값으로 가지고 그 장르의 노래별 재생 횟수를 리스트를 value 값으로 가지는 해시인 playlist_set을 만들도록 한다. 문제에서 제공하는 입출력 예시를 정리해보면 다음과 같이 만들어 진다.


sum_set= {'classic': 1450, 'pop': 3100}
playlist_set={'classic': [500, 150, 800], 'pop': [600, 2500]}


sum_set의 item 리스트를 가져와서 value 값을 기준으로 정렬을 한 뒤에 정렬된 key 값으로 playlist_set에 접근을 하도록 한다. playlist_set의 value 값을 정렬한 뒤에 맨 뒤의 두 값이 최대값들이므로 이를 이용해서 plays에서 인덱스 값을 찾아서 answer에 넣어주면 된다. 다만 기준 3에 의해서 재생 횟수가 같다면 고유 번호가 낮은 노래를 먼저 수록해야 하므로 최대값들이 같을 때와 다를 때를 구분해서 넣어주면 된다. plays에서 인덱스 값을 찾는 것은 index 내장함수를 사용했다. index 내장 함수는 시작점을 지정해줄 수 있으므로 재생 횟수가 같다면 두번째 최대값은 첫번째 최댓값의 인덱스 이후로 탐색하면 되기 때문이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(genres,plays):
    sum_set={}
    playlist_set={}
    answer=[]
    for i in range(len(genres)):
        if genres[i] in sum_set:
            sum_set[genres[i]]+=plays[i]
            playlist_set[genres[i]].append(plays[i])
        else:
            sum_set[genres[i]]=plays[i]
            playlist_set[genres[i]]=[plays[i]]
    sum_list=sorted(list(sum_set.items()),key=lambda x:x[1],reverse=True)
    for i in sum_list:
        temp=sorted(playlist_set[i[0]])
        if len(temp)>=2:
            if temp[-1]==temp[-2]:
                answer.append(plays.index(temp[-1]))
                answer.append(plays.index(temp[-2],plays.index(temp[-1])+1))
            else:
                answer.append(plays.index(temp[-1]))
                answer.append(plays.index(temp[-2]))
        else:
            answer.append(plays.index(temp[0]))
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers] Lv 3. 멀리 뛰기  (0) 2019.03.11
[Programmers]Lv 2.폰켓몬  (0) 2019.03.10
[Programmers]Lv 2.땅따먹기  (0) 2019.03.08
[Programmers] Lv 3. 등굣길  (2) 2019.03.07
[Programmers]Lv 2.다음 큰 숫자  (0) 2019.03.06
728x90
반응형

문제:

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


728x90
반응형
저작자표시 비영리 동일조건

'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
728x90
반응형

문제:

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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


728x90
반응형
저작자표시 비영리 동일조건

'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

+ Recent posts

티스토리툴바