다시 방법을 찾고 있습니까? 나는 코드를 재사용하기로 되어 있었다 하하하 그러나 그것은 수학 문제였다. 시원한…
문제 설명
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 침수되지 않은 지역을 통해 학교에 가려고 합니다. 집에서 학교까지의 경로는 mxn 그리드로 나타낼 수 있습니다.
아래 그림은 m = 4 및 n = 3에 적용됩니다.
'추천 관련글,
집이 위치한 좌상단의 좌표는 (1, 1)로, 학교가 위치한 우하단의 좌표는 (m, n)으로 표현된다.
격자 크기 m, n과 물에 잠긴 영역의 좌표가 있는 2차원 배열 웅덩이가 매개변수로 제공됩니다. 그냥 오른쪽 아래로 움직이세요 집에서 학교까지의 최단 경로 수를 1,000,000,007로 나눈 나머지를 반환하는 솔루션 함수를 작성하세요.
제한
- 그리드 크기 m과 n은 1에서 100 사이의 자연수입니다.
- m과 n이 모두 1이면 입력으로 제공되지 않습니다.
- 0개 이하 및 10개 이하의 침수 지역.
- 집과 학교가 침수된 경우는 입력으로 제공되지 않습니다.
I/O 예시
| 중 | N | 웅덩이 | 돌려 주다 |
| 4 | 삼 | ((2, 2)) | 4 |
I/O 예시 설명
설명
- 수학 문제인 줄 알았는데 웅덩이가 어디 있는지 알 수가 없네?
- 웅덩이가 학교를 막으면 웅덩이의 수가 적어도 학교에 갈 수 없습니다.
- 하지만 “집과 학교가 물에 잠겼을 때 입력으로 주어지지 않는다” ㅋㅋ
- 그럼 수학은? 다시 웃다
- 하지만 “집과 학교가 물에 잠겼을 때 입력으로 주어지지 않는다” ㅋㅋ
- 웅덩이가 학교를 막으면 웅덩이의 수가 적어도 학교에 갈 수 없습니다.
- 그럼에도 불구하고 웅덩이의 위치에 따라 갯수와 상관없이 답은 같을 수 있다.
- 지금 하면 안되나요???
- 필요 없습니다. 오른쪽과 아래로만 이동할 수 있으므로 지도를 보정할 필요가 없습니다.
- 지금 하면 안되나요???
- 그리고 그 문제는
- 조정 문제
- mxn, 여기서 m은 수평이고 n은 수직이며,
- 웅덩이의 좌표가 ((2,2))로 주어졌으나 어느 것이 수평인지 수직인지는 말하지 않은 점
- 상식적으로 보통 mxn은 수평과 수직이고 웅덩이도 수평과 수직이라고 생각하는데…
- 누가 거꾸로 생각하겠습니까? (실수로 잘못 코딩한 경우 즉시 맞음)
- 두번째는 최단거리…
- 어차피 좌우로만 이동할 수 있으니까… 그냥 걸어가면 최단거리인데…
- 조정 문제
- 결론은 DP로 갑니다.
- 오른쪽과 아래에 두 개의 닌자 클론을 사용하는 문제와 답은 얼마나 많은 클론이 학교에 도착하는지입니다.
- 집에서 처음으로
- 오른쪽 도로가 비어 있으면 클론을 오른쪽으로 가져갑니다. 게시됨
- 아래쪽 거리도 비어 있으면 아래쪽 거리에도 복제본을 보냅니다.
- 분신이 움직이면 본체와 마찬가지로 우측 하단에 분신을 생성한다.
- 학교에 도착하는 각 클론에 대해 +1
- 집에서 처음으로
- 1000000007로 나누는 것을 잊지 마십시오.
- 아이디어가 끝났습니다. 이제 무식한 코딩 가주!
- 오른쪽과 아래에 두 개의 닌자 클론을 사용하는 문제와 답은 얼마나 많은 클론이 학교에 도착하는지입니다.
- 무지해서…???
- 모든 정확도 테스트는 통과하지만 효율성 테스트는 모두 실패합니다… 이상하죠?
정확성 테스트
테스트 1 〉 통과 (0.02ms, 10.1MB)
테스트 2 〉 통과 (0.03ms, 10.4MB)
테스트 3 〉 통과 (0.04ms, 10.2MB)
테스트 4 〉 통과 (0.14ms, 10.4MB)
테스트 5 〉 통과 (0.17ms, 10.2MB)
테스트 6 〉 통과 (0.11ms, 10.3MB)
테스트 7 〉 통과 (0.21ms, 10.4MB)
테스트 8 〉 통과 (0.28ms, 10.6MB)
테스트 9 〉 통과 (0.11ms, 10.4MB)
테스트 10 〉 통과 (0.02ms, 10.2MB)
효율성 테스트
테스트 1 〉 실패 (23.34ms, 10.6MB)
테스트 2 〉 실패 (7.10ms, 10.4MB)
테스트 3 〉 실패 (9.52ms, 10.5MB)
테스트 4 〉 실패 (13.87ms, 10.4MB)
테스트 5 〉 실패 (12.20ms, 10.4MB)
테스트 6 〉 실패 (23.99ms, 10.5MB)
테스트 7 〉 실패 (8.48ms, 10.4MB)
테스트 8 〉 실패 (15.59ms, 10.4MB)
테스트 9 〉 실패 (17.96ms, 10.4MB)
테스트 10 〉 실패 (15.38ms, 10.4MB)- 코드는 아무리 봐도 뭐가 문제인지 모르겠어…ㅋㅋㅋㅋ
- 그리고 댓글 다 지웠는데.. 왜 저렇게 써져있지? 착란
def solution(m, n, puddles):
닌자스 = ()
지도 = ((0 for _ in range(m)) for _ in range(n) )
닌자스.append((0,0))
지도(0)(0) = 1
for puddle in puddles:
x, y = puddle
지도(y-1)(x-1) = -1
while len(닌자스) > 0:
닌자수 = len(닌자스)
for i in range(닌자수):
x,y = 닌자스.pop(0)
if x < m-1 and 지도(y)(x+1) != -1:
지도(y)(x+1) += 지도(y)(x)
if (x+1,y) not in 닌자스:
닌자스.append((x+1,y))
if y < n-1 and 지도(y+1)(x) != -1:
지도(y+1)(x) += 지도(y)(x)
if (x,y+1) not in 닌자스:
닌자스.append((x,y+1))
return 지도(n-1)(m-1) #학교에도착한분신갯수- 바보같이 시간낭비. ㅋㅋㅋ
- 돌아와서 백분율을 1000000007로 나눈 값을 전달합니다. 하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하
- 시간 낭비였어
- 돌아와서 백분율을 1000000007로 나눈 값을 전달합니다. 하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하하
def solution(m, n, puddles):
닌자스 = ()
지도 = ((0 for _ in range(m)) for _ in range(n) )
닌자스.append((0,0))
지도(0)(0) = 1
for puddle in puddles:
x, y = puddle
지도(y-1)(x-1) = -1
while len(닌자스) > 0:
닌자수 = len(닌자스)
for i in range(닌자수):
x,y = 닌자스.pop(0)
if x < m-1 and 지도(y)(x+1) != -1:
지도(y)(x+1) += 지도(y)(x)
if (x+1,y) not in 닌자스:
닌자스.append((x+1,y))
if y < n-1 and 지도(y+1)(x) != -1:
지도(y+1)(x) += 지도(y)(x)
if (x,y+1) not in 닌자스:
닌자스.append((x,y+1))
return 지도(n-1)(m-1) % 1000000007 #학교에도착한분신갯수- 석사코드…. 효율이 빠릅니다
- 아.. 인덱스 오류를 방지하기 위해 상단에 다른 행을 만듭니다. 대박이다.
- 닌자를 먼저 보내고 위쪽/왼쪽에서 값을 추가해 보았습니다…
- 몇 번 해보고 코드 오류 나서 포기했는데… 지금 와 보니 그렇게 하는게 편하네요.
- 웅덩이를 확인할 필요 없이 값을 추가하기만 하면 됩니다.
- 아.. 인덱스 오류를 방지하기 위해 상단에 다른 행을 만듭니다. 대박이다.
def solution(m,n,puddles):
grid = ((0)*(m+1) for i in range(n+1)) #왼쪽, 위로 한줄씩 만들어서 IndexError 방지
if puddles != (()): #물이 잠긴 지역이 0일 수 있음
for a, b in puddles:
grid(b)(a) = -1 #미리 -1로 체크
grid(1)(1) = 1
for j in range(1,n+1):
for k in range(1,m+1):
if j == k == 1: #(1,1)은 1로 만들어두고, 0이 되지 않도록
continue
if grid(j)(k) == -1: #웅덩이는 0으로 만들어 다음 덧셈 때 영향끼치지 않게
grid(j)(k) = 0
continue
grid(j)(k) = (grid(j)(k-1) + grid(j-1)(k))%1000000007 #(a,b) = (a-1,b) + (a,b-1) 공식
return grid(n)(m)
정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.1MB)
테스트 2 〉 통과 (0.02ms, 10.1MB)
테스트 3 〉 통과 (0.02ms, 9.93MB)
테스트 4 〉 통과 (0.04ms, 9.96MB)
테스트 5 〉 통과 (0.05ms, 10MB)
테스트 6 〉 통과 (0.04ms, 9.99MB)
테스트 7 〉 통과 (0.06ms, 10MB)
테스트 8 〉 통과 (0.07ms, 10.1MB)
테스트 9 〉 통과 (0.04ms, 10.3MB)
테스트 10 〉 통과 (0.02ms, 10.1MB)
효율성 테스트
테스트 1 〉 통과 (2.23ms, 10.3MB)
테스트 2 〉 통과 (1.17ms, 10.3MB)
테스트 3 〉 통과 (1.08ms, 10.2MB)
테스트 4 〉 통과 (1.99ms, 10.2MB)
테스트 5 〉 통과 (1.64ms, 10.4MB)
테스트 6 〉 통과 (2.41ms, 10.3MB)
테스트 7 〉 통과 (1.19ms, 10.3MB)
테스트 8 〉 통과 (1.72ms, 10.2MB)
테스트 9 〉 통과 (1.96ms, 10.4MB)
테스트 10 〉 통과 (1.92ms, 10.3MB)- 그리고 사전으로 그렇게 하는 사람들이 있습니다.
- 왜 사전을 사용합니까? 근데 내 코드보다 빠르다 ㅋㅋㅋㅋㅋㅋㅋ
def solution(m, n, puddles):
answer = 0
info = dict((((2, 1), 1), ((1, 2), 1)))
for puddle in puddles:
info(tuple(puddle)) = 0
def func(m, n):
if m < 1 or n < 1:
return 0
if (m, n) in info:
return info((m, n))
return info.setdefault((m, n), func(m - 1, n) + func(m, n - 1))
return func(m, n) % 1000000007
정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.1MB)
테스트 2 〉 통과 (0.02ms, 10.2MB)
테스트 3 〉 통과 (0.03ms, 10.1MB)
테스트 4 〉 통과 (0.03ms, 10.1MB)
테스트 5 〉 통과 (0.10ms, 10.1MB)
테스트 6 〉 통과 (0.05ms, 10MB)
테스트 7 〉 통과 (0.06ms, 10.3MB)
테스트 8 〉 통과 (0.14ms, 10MB)
테스트 9 〉 통과 (0.11ms, 10MB)
테스트 10 〉 통과 (0.01ms, 10.2MB)
효율성 테스트
테스트 1 〉 통과 (5.32ms, 11.1MB)
테스트 2 〉 통과 (2.23ms, 10.7MB)
테스트 3 〉 통과 (2.70ms, 10.6MB)
테스트 4 〉 통과 (3.95ms, 11.2MB)
테스트 5 〉 통과 (3.34ms, 10.6MB)
테스트 6 〉 통과 (5.40ms, 11.2MB)
테스트 7 〉 통과 (2.53ms, 10.5MB)
테스트 8 〉 통과 (4.03ms, 11.1MB)
테스트 9 〉 통과 (4.21ms, 11.1MB)
테스트 10 〉 통과 (4.21ms, 11.1MB)- 어쨌든 특종이므로 적어두자.
- 경우의 수로 해결할 수 있다고 틀렸어
- 웅덩이의 위치 때문에 길을 찾으려 했을 뿐
- 이전 결과에 추가하는 것이 추가 될 것이라고 생각했습니다.
- 구현코드 버그 수정해서 닌자 또 보내게 한 결과 ㅋㅋㅋㅋ
- 다음에 그것에 대해 조금 더 생각해보고 이와 같은 코드를 작성해 봅시다.
- 완전 깨끗해요…
def solution(m, n, puddles):
# dp table 생성 - padding
dp = ((0 for i in range(m + 1)) for _ in range(n + 1))
# 출발지점 및 웅덩이 처리
dp(1)(1) = 1
for puddle in puddles:
dp(puddle(1))(puddle(0)) = -1
# dp table 완성
for i in range(1, n+1):
for j in range(1, m+1):
# 만약 웅덩이라면
if dp(i)(j) == -1:
dp(i)(j) = 0
continue
dp(i)(j) += dp(i-1)(j) + dp(i)(j-1)
return dp(n)(m) % 1000000007