2*n짜리 직사각형을 1*2, 2*1, 2*2 짜리로 채우는 방법의 갯수를 구하기 가장 끝에 1*2, 2*1를 두는 각각의 방법을 d[n-2], d[n-1] 라고 한다. 이때, 끝이 1*2를 두개 두는 것은 2*2를 하나 두는 것과 같다. 즉, d[n-2]에 대해 2가지 경우가 있는 것이므로 d[n]=d[n-2]*2 + d[n-1] 이다. n=1일 때 1(2*1짜리 하나)로 재귀를 빠져나온다. n=2일 때 3(1*2짜리 두 개, 2*2짜리 하나)로 재귀를 빠져나온다. import java.util.Scanner; public class BOJ11727 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int x=sc..
분류 전체보기
주어진 수열 내에서 증가하는 부분수열 LIS 중 최대길이와 그 수열 구하기 - 주어진 수열 a[]와 수열의 i번째 수까지의 LIS 최대길이를 저장하는 d[]를 생성 - i번째 수가 LIS가 성립하도록 영향을 준 수열의 인덱스를 v[i]에 저장함 - 부분수열이 존재하지 않을 때의 기본값인 1로 d[]를 초기화함 - 2부터 수열의 길이 n까지 반복하여 d[]에 값을 저장한다. - 인덱스 i 이하인 수 j 중에서 a[i]보다 크면서, d[i]-1보다 큰 d[j]를 찾으면 d[i]=d[j]+1 로 업데이트한다. - 이때, v[i]에 인덱스 j를 저장한다. - 저장된 d[] 에서 최대값이 존재하는 LIS의 최대길이이다. - d[]의 최대값을 가진 수의 인덱스를 ansIndex에 저장하고, a[ansIndex]를 ..
1,2,3의 합으로 연속하지 않고 주어진 수를 표현하는 방법 출력하기 - 입력될 수 있는 모든 경우의 수를 저장하기 위해, 2차원 배열 d[100001][4] 로 메모이제이션을 한다. - d[i][j]는 합해서 i 가 되는 방법 중, 마지막으로 더해지는 수가 j 이다. - 즉, 합해서 i 가 되는 방법의 수는 d[i][1]+d[i][2]+d[i][3] 이다. - d[1][1], d[2][2], d[3][3]는 예외로 처리하기 위해 if(i == j)일 때는 1을 저장하도록 처리한다. - d[i][1]를 구하려면, 마지막에 더해지는 수 1을 제외하고 (i-1)에 대한 방법의 수를 구하면 된다. - 이때, 1과 연속이 되지 않기 위해 (i-1)에 대한 방법은 d[i-1][2], d[i-1][3] 두 가지만 ..
N개의 카드를 1~N개짜리 카드팩으로 고를 때 가장 싸게 사는 가격을 찾기 - 1~n개의 카드가 들어있는 카드팩의 가격을 p[1]~p[n] 배열에 저장한다. - 1~n개의 카드를 고를 때 가장 싸게 가격을 d[1]~d[n] 배열에 저장한다. - 모든 d[ ] 배열에 초기값은 최대가격을 초과한 10,001로 설정한다. - if(d[x] < 10,001)으로, 메모리제이션을 확인한다. - x개를 고를 때, x-1개를 가장 싸게 사고, 1개짜리 카드팩을 사는 경우, x-2개를 가장 싸게 사고, 2개짜리 카드팩을 사는 경우, ... 0개를 가장 싸게 사고, x개짜리 카드팩을 사는 경우까지 가격을 반복문으로 비교하며 최저 가격을 d[x]에 저장한다. import java.util.Scanner; public cl..
여러개의 수들의 GCD 총 합 구하기, 오답처리 시 int범위 초과 고려해야함. 유클리드 호제법으로 GCD를 쉽게 구할 수 있으나, 최대 입력 100개가 모두 최대 정수 1,000,000일 경우의 GCD는 49.5억으로 int범위를 벗어난다. 자바는 int의 최대 양수 범위에서 벗어난 만큼 int의 최소 음수에 더해지므로, 런타임에러가 아닌 오답처리가 된다. 즉, 오답처리가 되었다면 데이터 타입의 범위가 넘어간 경우일 수 있으니 참고한다. import java.util.Scanner; public class BOJ9613 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t=sc.nextInt(); whi..
소스트리를 멀쩡히쓰다가 갑자기 픽- 꺼져버린다. 난 맥 에어 m1칩을 사용중이고.. 메인쓰레드와 충돌이라고하는데 검색해보니 보통 커밋할때 오류나거나? 계정 연동, 키체인에 문제가 있는 경우가 많은데 나는 그냥 커밋멘트쓰다가도 픽 꺼지고, 아무것도 안하고 걍 켜놓기만 하다가도 픽 꺼짐 ;; ㅠㅠ 비슷한현상이신분 없나요 장시간 켜놓으면 꺼지나?... 그렇게 장시간도 아닌데.. 연동해놓은게 많아서 메모리초과되나..? 흠...
