떵호
seongho'Dev
떵호
전체 방문자
오늘
어제
  • 분류 전체보기 (116)
    • 회고 (2)
    • Algorithm (74)
      • 프로그래머스 (65)
      • 백준(BOJ) (2)
      • Note (7)
    • 기술독서 (25)
      • Clean Code (11)
      • 자바의 정석 (8)
      • 대규모 시스템 설계 기초 (6)
    • Computer Science (1)
      • Operating System (1)
    • Typescript (1)
    • JAVA (0)
    • Spring (6)
      • JPA (6)
    • AWS (2)
    • Git (2)
    • Etc (2)

블로그 메뉴

  • github

티스토리

태그

  • 클린코드
  • 자바의 정석
  • 알고리즘
  • 구현
  • JPA
  • 코딩테스트 준비
  • 프로그래머스
  • 카카오 코테
  • 완전탐색
  • Clean Code
hELLO · Designed By 정상우.
떵호
Algorithm/프로그래머스

[Java] 프로그래머스 Lv2 - 3 x n 타일링

[Java] 프로그래머스 Lv2 - 3 x n 타일링
Algorithm/프로그래머스

[Java] 프로그래머스 Lv2 - 3 x n 타일링

2022. 6. 2. 16:37
728x90

🔗 문제링크

 

코딩테스트 연습 - 3 x n 타일링

 

programmers.co.kr

📂 분류

DP

💡 풀이

이 문제는 2 x n 타일링을 응용한 문제이다.

 

세로 길이가 3인 바닥이기 때문에 n이 홀수 일 경우 타일 배치를 하지못한다.

처음 점화식은 dp[i] = dp[i - 2] * 4 - dp[i - 4]로 쉽게 구해졌으나 나머지 연산에 문제가 있어서 이 점화식으로는 문제를 해결하지 못했다. 다른 점화식을 구하려고 고민을 했으나 생각이 나지않아 풀이법을 참고해서 풀었다. 점화식은 다음과 같다.

tiles[i] = tiles[i - 2] * 3 + tiles[i - 4] * 2 + tils[i - 6] * 2 ...

💻 코드

public class Solution {

    private static final int MOD = 1000000007;

    public int solution(int n) {
        long[] tiles = new long[n + 1];

        tiles[0] = 1;
        tiles[2] = 3;

        for (int i = 4; i <= n; i += 2) {
            tiles[i] = tiles[i - 2] * 3;
            for (int j = i - 4; j >= 0 ; j -= 2) {
                tiles[i] += (tiles[j] * 2);
            }
            tiles[i] %= MOD;
        }

        return (int) tiles[n];
    }
}
728x90
저작자표시 (새창열림)

'Algorithm > 프로그래머스' 카테고리의 다른 글

[Python] 프로그래머스 Lv2 - 양궁대회 (2022 KAKAO BLIND RECRUITMENT)  (0) 2022.06.10
[Java] 프로그래머스 Lv2 - [3차] 압축 (2018 KAKAO BLIND RECRUITMENT)  (0) 2022.06.09
[Java] 프로그래머스 Lv2 - 2 x n 타일링  (0) 2022.05.31
[Java] 프로그래머스 Lv2 - 가장 큰 정사각형 찾기  (0) 2022.05.30
[Java] 프로그래머스 Lv2 - [3차] 방금 그 곡 (2018 KAKAO BLIND RECRUITMENT)  (0) 2022.05.29
  • 🔗 문제링크
  • 📂 분류
  • 💡 풀이
  • 💻 코드
'Algorithm/프로그래머스' 카테고리의 다른 글
  • [Python] 프로그래머스 Lv2 - 양궁대회 (2022 KAKAO BLIND RECRUITMENT)
  • [Java] 프로그래머스 Lv2 - [3차] 압축 (2018 KAKAO BLIND RECRUITMENT)
  • [Java] 프로그래머스 Lv2 - 2 x n 타일링
  • [Java] 프로그래머스 Lv2 - 가장 큰 정사각형 찾기
떵호
떵호

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.