1057: 걸기 쉬운 전화번호

Link : judge.koreatech.ac.kr/problem.php?id=1057

---

1. 문제

• 전화번호의 다이얼은 대부분 아래와 같이 생겼습니다.
  
  걸기 쉬운 전화번호는, 전화번호가 서로 인접해 있는 번호들로 이어져 있을 때 이를 걸기 쉬운 전화번호 라고 합니다. 같은번호가 연속되어있는 999 같은 번호는 쉬운 번호가 아닙니다.
  1256 같이 상/하/좌/우 로 이어져 있는 번호로 누를 수 있을 때 걸기 쉬운 전화번호 라고 합니다.
  1252 같이 눌렀던 번호를 또 누를 수도 있습니다.
  1569 는 1에서 5로가기 위해서 대각으로 가야하기 때문에 누르기 쉽지 않습니다.
  길이가 L인 걸기 쉬운 전화번호가 몇가지 있는지 구해주세요.

 

---

2. 문제의 조건

• 1 <= T <= 100
• 1 <= L <= 100
• 1,000,000,007로 나눈 나머지를 출력

 

---

3. 문제 접근

• 시간 복잡도
  
  시간 제한 1초에 T개 100개, L이 100개이므로 O(N^2) 이내로 풀어야 합니다.

 

• 아이디어
  
  1부터 시작하는 길이가  4인 것을 표시해보면
  맨 윗줄은 length(길이)입니다.
  
  

  4	3	2	1
  1	2	1	2
  1	2	1	4
  1	2	3	2
  1	2	3	6
  1	2	5	2
  1	2	5	4
  1	2	5	6
  1	2	5	8
  1	4	1	2
  1	4	1	4
  1	4	5	2
  1	4	5	4
  1	4	5	6
  1	4	5	8
  1	4	7	4
  1	4	7	8

  이 됩니다.
  1로 갈 수 있는 곳은 [2, 4]
  2로 갈 수 있는 곳은 [1, 3, 5]
  4에서 갈 수 있는 곳은[1, 5, 7] 이런 규칙성이 보입니다.
  
  이런 규칙성을 나열해보면
  

  번호	갈 수 있는 번호
  1	2 4
  2	1 3 5
  3	2 6
  4	1 5 7
  5	2 4 6 8
  6	3 5 9
  7	4 8
  8	5 7 9 0
  9	6 8
  0	8

  가 보입니다.
  또한, len이 2에서 number 1인경우 [2개(굵은 파란색)]로 총 2가지 밖에 갈 수 없다는 부분이 나옵니다.
  그러면 dp[number][len] = 2 가 되는 것입니다.
  dp[4][3] 길이가 3인 4번숫자에서 만들 수 있는 수는 [8개(굵은 붉은색)] 입니다.
  
  이때, [4][3] 중 밑줄 친 부분을보면 2개의 굵은 파란색과 겹치는 부분이 보입니다. 이 부분을 메모이제이션을 이용하여 중복 계산을 피해야합니다.

 

---

4. 풀이 방법

• 2차원 배열을 이용해 dp[번호][길이] 를 선어해줍니다.
  이는 "0번 번호에 길이가 3인 경우의 수는 n개 있다." 라고 메모이제이션 방식을 이용하여 저장하는 것입니다.
• 0번~9번 숫자까지 for을 이용해 돌려줍니다.
• 재귀함수 작성[dict로 여러 케이스를 만들어줌]
  만약 length가 1이면 갈 수 있는 곳은 없습니다. 그러므로 1을 반환해야합니다.
  만약 dp[number][length]가 0이아니라면 이미 계산한 적이 있으므로 계산된 값을 반환합니다.
  
  해당 number에서 갈 수 있는 번호를 뽑아 len - 1 만큼 하여 다시 재귀를 호출합니다.
  나온 결과값은 result에다 더해주시면서 조건에따라 1000000007로 나눈 나머지를 저장합니다.
• 계산이 끝났으면 계산한 값을 dp에 넣어줍니다.
  
  

 

---

5. 소스코드

• cjw-git.tistory.com/47

 

---

 

cjw.git@gmail.com