반응형 C/C++2 [BOJ 1463] 1로 만들기 (2가지 풀이/DP/BFS) (C++) www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 구현 방법 (DP 풀이) 이 문제는 전형적인 DP(Dynamic Programming) 문제입니다. DP문제를 해결하는 순서는 다음과 같습니다. 테이블 정의하기 점화식 찾기 초기값 정하기 이 문제에서 위 순서를 따라 답을 찾아보겠습니다. 테이블 정의하기 이 문제에서 테이블은 "D [i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값"이라고 정의할 수 있습니다. 테이블이란 이 문제에서 사용할 배열과 배열에 들어가는 각 값들의 의미입니다. 즉, 배열 d의 i번째에 들어가는 값은, i를 1로 만들기 위해 필요한 연산 .. 2021. 5. 1. [BOJ 5904] Moo 게임 (C++) www.acmicpc.net/problem/5904 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 구현 방법 처음에 이 문제를 봤을 때, 재귀를 통해 moo수열 문자열을 만들어서, 입력한 n 번째의 알파벳을 출력하면 되는 줄 알았습니다. 재귀를 통해 Moo 수열을 구현하는 코드를 성공적으로 짜고 기뻐하면서 제출했을때, 결과는 메모리 초과였습니다. 생각해보니 입력 n은 최대 1억 까지 가능한데, 길이가 1억인 수열을 구하려면 재귀를 너무 많이 돌아야 돼서 메모리 초과가 날 .. 2021. 4. 30. 이전 1 다음 반응형
