본문 바로가기

분류 전체보기18

[프로그래머스] 하노이의 탑 - JAVA 문제https://school.programmers.co.kr/learn/courses/30/lessons/12946전략하노이의 탑은 유명한 재귀 문제기둥이 3개인 것 기준 3개의 원판을 3번째 기둥으로 옮기려면위의 2개의 원판이 가운데 기둥에 옮겨져야 한다.그 후에 1번째 기둥의 마지막 원판을 마지막 3번째로 옮기고2번째 기둥의 원판 2개를 3번째로 옮긴다. → 이때 1번 스텝에서 2개의 원판이 가운데 기둥으로 옮겨지는 것은 출발지,나머지,도착지 기둥의 관점에서 보면 전체 1~3의 과정이 몇번째 기둥이 나머지, 도착지 기둥인지 옮겨지는 위치만 달라지고 전체 양상은 똑같다. → 어차피 마지막 3번째 원판은 모든 다른 원판보다 크니 위의 2개의 원판을 움직이는 것에 아무 영향이 없다. → 그렇게 3개의 원.. 2024. 9. 6.
[백준] 계단 수 1562 - JAVA 문제https://www.acmicpc.net/problem/1562전략N = 100 → 완전탐색으로는 불가능dp로 고민하자처음에는 dp[i][j]로 i : i자리 수 중 , 마지막이 j로 끝나는 계단수로 설정단순히 dp[i-1][j-1] + dp[i-1][j+1]로 더하면 계단수가 나올것이라는 생각하지만 989898989와 같이 계단수로 이루어져있지만 모든 자리수가 나오지 않는 경우가 있어 각 자리 수의 방문체크가 필요하다는 판단dp[i][j][k| 1dp[i-1][j-1][k] + dp[i-1][j+1][k] 로 모든 j-1, j+1을 끝자리로 가지는 모든 방문 여부를 확인한 수들을 다 더해준다ex) 989898989의 경우와 789898989의 경우 모두 확인따라서 길이가 N이면서 0부터 9까지 숫.. 2024. 9. 3.
[백준] 암호코드 2011 - JAVA 문제https://www.acmicpc.net/problem/2011전략5000자리이기때문에 완전탐색은 불가능입력값이 크기 때문에 dp로 생각해보면 앞에서 부터 끊어서 확인해보ex) 25114의 경우 - B,Y,A,K,A,D,N 의 알파벳들이 끊었을 때 나올 수 있다.-> 2/5/1/1/4 , 25/1/1/4, 25/11/4, 25/1/14, 2/5/11/4, 2/5/1/14dp[i] = i자리 영어의 암호화 가짓수로 두기맨 마지막 숫자를 확인 했을 때, 아래와 같이 확인할 수 있다.새로 붙인 숫자가 1~9를 앞에 수와 별도로 칠때 d[i-1]의 가짓수를 가진다.,앞에 숫자와 포함해 10 ~ 26 ->이 경우 앞에 숫자와 포함하기 때문에 가짓수는 d[i-2]코드import java.io.BufferedR.. 2024. 8. 23.
[백준] 타일 채우기 2133 - JAVA 문제https://www.acmicpc.net/problem/2133전략N = 2 -> 3 N = 4 -> 11 N = 6 -> 41 N이 홀수일 때는 0 N+2가 될수록 dp[i-2]와는 별도로 양끝을 세로막대로 채우고 가운대를 가로로 다 채운 형태의 2가지 경우가 추가된다. 1001    00001001    10010000   1001즉, N+2가 될때마다 i-2와 앞선 가운대를 다 채운 별도의 경우 수 그리고 i자체가 가운대를 채운 수를 고려해야 한다.정리하면, dp[i] = dp[i-2] * 3 + dp[4부터(i-2)까지 경우의 수] * 2의 합 + 2;코드import java.io.BufferedReader;import java.io.IOException;import java.io.Input.. 2024. 8. 22.

티스토리툴바