기본 콘텐츠로 건너뛰기

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

package programmers;

import java.util.stream.IntStream;
public class _3_x_n_타일링_230618 {

/*
동적 계획법(Dynamic Programming)을 사용하여 문제를 해결합니다.

해당 문제는 3 x n 크기의 바닥을 2 x 1 크기의 타일로 채우는 방법의 수를 구하는 문제입니다.
직사각형 타일은 가로로 배치하거나 세로로 배치할 수 있습니다.

해당 코드에서는 동적 계획법을 활용하여 문제를 해결합니다.
우선, 가로의 길이가 1인 경우는 2가지 방법이 가능하므로 dp[1] 2로 초기화합니다.
가로의 길이가 2인 경우는 3가지 방법이 가능하므로 dp[2] 3으로 초기화합니다.

이후, dp[i] dp[i-1] dp[i-2]의 값을 활용하여 계산됩니다.
i가 짝수인 경우(i%2 == 0)에는 이전의 경우의 수(dp[i-1] dp[i-2])를 더해서 계산합니다.
i가 홀수인 경우에는 dp[i-1]의 경우의 수에 2를 곱하고 dp[i-2]의 경우의 수를 더해서 계산합니다.

마지막으로, dp[i] 1000000007로 나눈 나머지를 구하여 저장합니다.
이는 문제에서 요구하는 방법의 수를 구하는 과정에서 숫자가 매우 커지는 것을 방지하기 위함입니다.

마지막으로, dp[n]을 반환하여 주어진 n에 대한 방법의 수를 출력합니다.

예를 들어, n 8인 경우를 예로 들면, dp[1] dp[2]는 이미 초기화되어 있고,
dp[3]부터 dp[8]까지의 값을 계산하여 결과를 반환합니다.
최종적으로 dp[8]의 값인 22를 반환합니다.
*/
public int solution(int n) {
int answer = 0;
int mod = 1000000007; //경우의 수를 나누려는 숫자

int[] dp = new int[n+1];

dp[1] = 2;
dp[2] = 3;

for(int i = 3; i <= n; i++){
if(i%2 == 0){
//짝수
dp[i] = dp[i-1]%mod + dp[i-2]%mod;
} else {
// 홀수
dp[i] = dp[i-1]*2%mod + dp[i-2]%mod;
}
dp[i] = dp[i]%mod;
}
return dp[n];
}



//아래 풀이는 시간 초과가 납니다.

/*
IntStream.rangeClosed(4, n): 4부터 n까지의 정수들로 이루어진 스트림을 생성합니다.
이 스트림은 4부터 n까지의 값을 가지고 있습니다.

filter(i -> i % 2 == 0): 스트림의 요소 중에서 짝수인 요소들만을 필터링합니다.
짝수인 경우에만 타일을 배치하므로, 홀수인 요소는 건너뜁니다.

forEach(i -> { ... }): 각 요소에 대하여 수행할 동작을 정의합니다.
여기서는 tile[i]를 계산하고 저장하는 역할을 합니다.

IntStream.rangeClosed(0, i - 4): 0부터 (i - 4)까지의 정수들로 이루어진 스트림을 생성합니다.
이 스트림은 0부터 (i - 4)까지의 값을 가지고 있습니다. 이는 세로로 배치된 타일의 개수에 해당합니다.

filter(j -> j % 2 == 0): 스트림의 요소 중에서 짝수인 요소들만을 필터링합니다.
짝수인 경우에만 세로로 배치된 타일의 개수를 고려합니다.

mapToLong(j -> tile[j] * 2): 짝수 인덱스 j에 대하여 tile[j]의 값을 가져와 2를 곱합니다.
이는 세로로 배치된 타일의 개수에 해당하는 tile[j] 값을 가져오고, 2를 곱하여 가로로 배치된 타일의 개수에 더해줍니다.

sum(): 계산된 값들의 합을 구합니다. 이는 세로로 배치된 타일과 가로로 배치된 타일의 개수를 합친 값을 의미합니다.

tile[i] %= mod: 계산된 tile[i]의 값을 mod로 나눈 나머지로 갱신합니다. 이는 경우의 수가 매우 커질 수 있으므로,
나머지 값을 사용하여 문제 조건에 맞게 결과를 반환합니다.

return tile[n]: 최종적으로 tile[n]의 값을 반환합니다. 이는 가로의 길이가 n인 바닥을 채우는 방법의 수를 의미합니다.
*/
long[] tile = new long[5001];

public long solution_timeout(int n) {
int mod = 1_000_000_007;

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

// 4부터 n까지의 짝수에 대해 반복
IntStream.rangeClosed(4, n)
.filter(i -> i % 2 == 0) // 짝수 필터링
.forEach(i -> {
// tile[i]를 계산
tile[i] = tile[i - 2] * 3 + IntStream.rangeClosed(0, i - 4)
.filter(j -> j % 2 == 0) // 짝수 필터링
.mapToLong(j -> tile[j] * 2) // 짝수 인덱스의 tile[j] 2를 곱함
.sum(); // 계산된 값들의 합을 구함
tile[i] %= mod; // 나머지 연산
});

return tile[n]; // tile[n] 반환
}


}


댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ *...

개발 공부 - PC 카카오톡 작업 표시줄 아이콘 이미지 변경 방법

PC 카카오톡 사용시 작업 표시줄에서 아이콘 이미지를 변경하는 방법이다. 1) 작업 표시줄 내 카카오톡 아이콘에서 마우스 오른쪽 버튼을 누른  뒤 속성에 들어간다. 2) 아이콘 변경에서  C:\Windows\system32\imageres.dll C:\Windows\system32\shell32.dll C:\Windows\system32\DDORes.dll C:\Windows\System32\moricons.dll (MS DOS Icons) 등을 누른 뒤 적당한 것을 선택하여 적용한다. * 사내 메신저 아이콘을 참고해도 된다. 참고 : 기본 아이콘 위치 https://blog.silnex.kr/windowstip-windows-%EA%B8%B0%EB%B3%B8-%EC%95%84%EC%9D%B4%EC%BD%98-%EC%9C%84%EC%B9%98/ 2022. 11. 29.  생각보다 유입이 많아서 놀랐습니다. PC 카톡 사용자 화이팅!

운동 정보 - 어메이즈핏 밴드 5 스마트밴드 나이키 런 클럽(NRC = Nike Run Club) 연동

 나이키 런 클럽 쓰려고 산 어메이즈핏 밴드5 인데 연동이 영 어려워서 찾아보고 써봤다. 1. Zepp 앱은 연동이 되어 있어야 한다. 2.  Zepp 앱 -> 프로필 -> 내 기기 -> Amazfit Band 5 3. 검색 가능 : 켜짐 활동 심박수 공유 : 켜짐 연결 제한 : 꺼짐 (기본) 백그라운드에서 실행 : 제외로 등록 4. NRC(나이키 런 클럽) 앱 -> 설정 -> 러닝 설정 -> 기기 5. 심박수 표시 -> 블루투스에서 AmazFit Band 5 누르고 NRC 즐기면 된다! * 안드로이드 이용자입니다.