백준 2193번 자바
문제
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
import java.util.Scanner;
public class Main2193 {
static int N;
static long[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
dp = new long[N+1];
dp[1] = 1;
for (int i=2; i<=N; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[N]);
}
}1. 처음에 dp의 타입을 int형으로 선언했다가 오버플로우가 나면서 long으로 바꿨다. 하지만 백준에서 채점결과 틀렸습니다가 나왔을때 로직자체가 잘못된줄 알고 다른 글들을 보다가 기본형 크기의 문제라는 것을 알게됐다.
dp[n-1] + dp[n-2]를 더하는데 초기값이 1이기에 90이 되도 그다지 큰 수가 안될거라고 생각했던게 잘못된 생각이었다.
2. 0자리수 0개
1자리수 1개
2자리수 1개
3자리수 2개
4자리수 3개
5자리수 5개
6자리수 8개
6개 자리수까지 직접 구하고 수열을 발견해서 점화식을 세웠다. (i번째의 개수는 i-1 + i-2번째의 개수이다.)
이번에는 쉽게 수열을 발견해서 어렵지 않게 점화식을 세웠지만 여전히 dp문제는 쉽지 않은것 같다.
백준 2193 자바 - 이친수 (BOJ 2193 JAVA)
문제 : boj2193 1. N=1 일 때를 생각해보자. 0으로 시작하면 안되므로, 0으로 끝나는 수는 0개이고 1로 끝나는 수는 1개이다. (0과 1) 2. N=2 일 때를 생각해보자. 0으로 끝나려면 어떻게 해야 할까? 이 문
nahwasa.com
비슷한 방식으로 접근했지만 배열을 사용하지 않아 메모리를 아낀다. 이런식으로 푸는 전제 조건으로 dp를 bottom-up방식으로 풀어 나갈때 n-1, n-2만 필요하는 것을 캐치하는 것이 중요하다.
정리 : 정답을 맞추는거랑 별개로 다방면에서 생각을 해야 실력이 많이 늘어날 것이다. 계속해서 사고를 유연하게 유지할 수 있게 항상 고민하자.