[BAEKJOON] 1463번 1로 만들기

문 제

 

소 스  코 드

#include <iostream>
#include <algorithm>

int main() {
	int N;
	std::cin >> N;

	int *temp{ new int[N + 1] };
	
	temp[1] = 0;
	temp[2] = 1;	// 2일 때 /2, -1
	
	for (int i = 3; i < N + 1; ++i) {
		if	(0 == (i % 6))		
        		temp[i] = std::min({ (temp[i - 1] + 1), (temp[i / 2] + 1), (temp[i / 3] + 1) });
		else if (0 == (i % 3))		
        		temp[i] = std::min((temp[i - 1] + 1), (temp[i / 3] + 1));
		else if (0 == (i % 2))		
        		temp[i] = std::min((temp[i - 1] + 1), (temp[i / 2] + 1));
		else					
        		temp[i] = temp[i - 1] + 1;
	}

	std::cout << temp[N] << "\n";
	
	delete[] temp;
	return 0;
}

 

풀 이

 

• 재귀 호출을 통하여 구현하려고 하였지만 시간초과가 생겼습니다.

• 그래프로 그린다면 왼쪽은 i - 1, 오른쪽에는 2로 나눠진다면 i / 2, 3로 나눠진다면 i / 3,
  둘 다 나눠진다면 i / 2, i / 3을 가지고 있는데, 이때 누적으로 값을 계산한다면 메모리를 조금 낭비해서 시간이 빠르게 구현할 수 있습니다. 

 

결 과 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/1463