[Programmers]산 모양 타일링[JS]

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/258705

프로그래머스

 

접근방법

처음 문제를 읽고 어떻게 풀어야 할 지 감이 잡히지 않았다.

손으로 하나씩 그려보면서 규칙을 찾아보려 했는데.. 복잡하기도 하고 눈에 띄는 규칙도 안보였다.

구글링을 해서 답을 얻으려고 했지만 다른 블로그들을 보고도 이해하기가 쉽지 않았다.

그러다 카카오에서 작성한 해설을 보게 되었는데 가장 이해가 잘됐다!!

링크는 아래 첨부해두겠습니다~!

 

문제풀이

타일을 채울 수 있는 방법은 4가지가 있다.

아래 방향 정삼각형을 기준으로 생각해야 한다.

1. 위쪽 정삼각형과 함께 마름모 타일로 덮기
2. 왼쪽 정삼각형과 함께 마름모 타일로 덮기
3. 오른쪽 정삼각형과 함께 마름모 타일로 덮기
4. 정삼각형 타일로 덮기

- 1번 방법은 위에 삼각형이 존재할 때(tops[i]==1]만 사용할 수 있다.

- 3번 방법으로 정삼각형을 채운 경우, 다음 삼각형을 채울 때 2번의 방법을 사용할 수 없다.

위의 두가지 경우를 생각하면서 문제를 풀면 된다.

 

- a[]에는 3번의 방법을 사용한 경우의 수를 저장한다.

- b[]에는 3번을 제외한 방법을 사용한 경우의 수를 저장한다.

 

초기 값 설정

a[]는 3번의 방법을 사용한 경우이기 때문에 a[1] = 1을 저장한다.

b[1]는 top[0]의 값이 1이라면(위의 삼각형이 존재한다면) 3을 저장하고,

0이라면(위의 삼각형이 존재하지 않는다면) 2를 저장한다.

 

Case 1. 위의 삼각형이 존재하는 경우

a[k] = a[k-1] + b[k-1]

a[]에는 3번의 방법을 사용한 경우의 수를 저장하기 때문에, 이전에 3번의 방법을 사용했는지의 여부는 신경쓰지 않아도 된다.

 

b[k] = 2 * a[k-1] + 3 * b[k-1]

b[]의 경우는 이전에 3번을 사용했는 지의 여부를 신경써야한다.

- 이전에 3번을 사용했다면 1번과 4번의 방법을 사용할 수 있다.

  => 2 * a[k-1]

- 이전에 3번을 사용하지 않았다면 1번, 2번, 4번의 방법을 사용할 수 있다.

  => 3 * b[k-1]

 

Case 2. 위의 삼각형이 존재하지 않는 경우

a[k] = a[k-1] + b[k-1]

a[]에는 3번의 방법을 사용한 경우의 수를 저장하기 때문에, 위의 삼각형이 존재하는 지의 여부는 신경쓰지 않아도 된다.

따라서 Case 1과 Case 2에서 a[k]의 값은 동일하다.

 

b[k] = a[k-1] + 2 * b[k-1]

위의 삼각형이 존재하지 않는 경우이기 때문에 1번을 사용할 수 없다. 1번의 경우를 제외하고 생각하자.

- 이전에 3번을 사용했다면 4번의 방법만 사용가능하다.

  => a[k-1]

- 이전에 3번을 사용하지 않았다면 2번과 4번의 방법을 사용할 수 있다.

  => 2 * b[k-1]

 

 

정답코드

https://tech.kakao.com/2023/12/27/2024-coding-test-winter-internship/

2024 카카오 겨울 인턴십 코딩테스트 문제해설

function solution(n, tops) {
  var answer = 0;
  const MOD = 10007;
  let a = [];	// i번째 아래 방향 정삼각형을 3번으로 덮는 경우
  let b = [];	// i번째 아래 방향 정삼각형을 3번을 제외한 방법으로 덮는 경우
  // 초기 값 설정
  a[1] = 1;	
  b[1] = tops[0] == 1 ? 3 : 2;

  for (let i = 2; i <= n; i++) {
    a[i] = (a[i - 1] + b[i - 1]) % MOD;		// 3번으로 덮는 경우

    if (tops[i - 1] == 1) {		// 위의 삼각형이 존재하는 경우
      // i-1번째 삼각형을 3번으로 덮은 경우(1번과 4번 가능하므로 2를 곱해줌) -> 2 * a[i-1]
      // i-1번째 삼각형을 3번을 제외한 방법으로 덮는 경우(1번, 2번, 4번 가능하므로 3을 곱해줌) -> 3 * b[i-1]
      b[i] = (2 * a[i - 1] + 3 * b[i - 1]) % MOD;	
    }
    if (tops[i - 1] == 0) {		// 위의 삼각형이 존재하지 않는 경우
      // i-1번째 삼각형을 3번으로 덮는 경우(4번 가능)
      // i-1번째 삼각형을 3번을 제외한 방법으로 덮는 경우(2번과 4번 가능하므로 2를 곱해줌) -> 2 * b[i-1]
      b[i] = (a[i - 1] + 2 * b[i - 1]) % MOD;
    }
  }
  answer = (a[n] + b[n]) % MOD;	

  return answer;
}

느낀 점

카카오 인턴십 문제라는 생각때문인지 더욱 어렵게 느껴졌다.

무조건 명확한 규칙이 있을거다라고 생각하고 규칙을 찾으려 했는데 너무 어려웠다.

내가 느끼는 포인트는 아래 방향 정삼각형을 기준으로 생각해야 된다는 점이였다.

겹치는 부분인 오른쪽 마지막 삼각형을 어떻게 해줘야한다는 생각만으로 문제를 풀었는데 역시 안풀릴때는 생각의 전환이 필요한 것 같다.

오늘도 코테에 호되게 당하고.. 열심히 풀어야겠다는 것을 느꼈다..