[코딩테스트] 백준(BAEKJOON) - 이친수(Java, 2193번)

안녕하세요.

요즘 계속 DP알고리즘 문제도 다른사람의 풀이를 봐야지만 이해가 돼 한동안 풀이가 없었습니다.

이번에 만나볼 문제는 사실... 맞긴맞았는데 흔히 말하는 DP로 풀지는 못했습니다.

 

N=N-1+N번째항... 참 간단한 공식이지만 저는 생각지도 못한 범위였습니다.

 

생각은 맞는거같아서 해볼까 말까 고민하다가 그냥 질러봤는데 맞아서 기분이 아주 날아갈듯 합니다. 호호

그럼 문제부터 만나보실까요?

 

https://www.acmicpc.net/problem/2193

2193번: 이친수

그렇습니다.

문제는 읽어보시면 아실거라 생각합니다. 그럼이제 제가 생각한 풀이에 대해 적고자합니다.

 

다음은 언제나 그렇듯 제가 작성한 코드입니다.

 

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			
		Scanner sc=new Scanner(System.in);
		int count=sc.nextInt();
		
		long zero_count=0;
		long one_count=1;
		long temp=0;
		if(count==1)
		{
			System.out.println("1");
			return;
		}
		
		for(int i=2;i<=count;i++)
		{
			temp=zero_count;
			zero_count=zero_count+one_count;
			one_count=temp;
		}
		
		System.out.println(zero_count+one_count);
		
	}

}

예 그렇습니다. 아마 이게 무슨뜻이지 싶으실겁니다.

 

간단한 공식을 적자면

N번째의 끝자리가 0인 숫자 갯수=N-1번째의 끝자리가 0인 숫자 + N-1번째의 끝자리가 1인 숫자고

N번째의 끝자리가 1인 숫자 갯수=N-1번째의 끝자리가 0인 숫자

입니다. 해당 방법을 반복으로 나아가면 되겠습니다.

 

이친수 풀이

제가 생각한 내용을 글로 적어봤습니다.

생각정리를 했지만 나약해 아마 뭔말이지?싶으실 수도 있습니다.

ㅠㅠㅠ

 

그래도 풀었다는것에 감사하며

이번글 마무리하겠습니다.

 

감사합니다.

다들 새해복 많이 받으시고 올해드 즐거운 코딩하시길 바랍니다.💪💪