[C]백준_9625 : BABBA

Alal11·2022년 11월 28일
0
post-thumbnail

출처

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


문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?


입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.


출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.


예제 입출력


알고리즘 분류

  • 다이나믹 프로그래밍

➡️문제 분석

버튼 횟수화면 상태A 개수B 개수
0A10
1B01
2BA11
3BAB12
4BABBA23
5BABBABAB35

A -> B
B -> AB
으로 바뀐다.

현재 단계의 B 개수만큼 다음 단계의 A 개수가 되고,
현재 단계의 A 개수 + B 개수만큼 다음 단계의 B 개수가 된다.

예를 들어,
버튼 횟수가 3일 때, B는 2개이므로, 다음 단계 A는 2개가 되고, (A+B)개수는 3개이므로, 다음 단계 B는 3개가 된다.


➡️코드(⭕)

#include <stdio.h>

int main()
{
	int K = 0;
	int numA = 1, numB = 0;		// 처음 화면에 A만 1개 표시되어 있음
	int temp = 0;

	scanf("%d", &K);

	for (int i = 0; i < K; i++)
	{
		temp = numA;			// temp에 현재 A 개수를 넣음
		numA = numB;			// 다음 A 개수는 현재 B의 개수
		numB = temp + numB;		// 다음 B의 개수는 현재 A개수와 현재 B의 개수
	}

	printf("%d %d\n", numA, numB);

	return 0;
}

➡️코드 분석

버튼 횟수 K를 입력 받고, A의 개수는 처음부터 1개로 시작하므로 초깃값을 1로 설정해준다.

K번 만큼 반복문을 돌려주는데,

임시 변수 temp에 현재 A 개수를 넣고, 다음 A 개수인 numA에는 현재 B의 개수를 넣는다.

다음 B의 개수인 numB에는 temp와 현재 B 개수를 더한 값을 넣어준다.

K번 만큼 반복하고 난 후 numA와 numB 값을 출력해준다.


➡️end

오랜만에 C언어로 풀어봤다. 규칙만 찾으면 풀기엔 은근 쉬운 문제였다!

0개의 댓글