0과 1의 쉼터

문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.풀이N을 1로 만들기 위한 연산을 최소화하는 문제다.dp[i] : i를 만들기 위한 최소 연산 횟수 문제의 힌트를 보면 알 수 있듯 N을 1로 만드는 방법에서는 단순한 점화식이 나오지 않는다.1을 N으로 만드는 방법을 생각해보자.dp[i] = dp[i - 1] + 1는 기본값으로 가진다.d..

문제상근이는 선영이와 함께 게임을 하고 있다. 먼저, 상근이는 두 양의 정수 A와 B를 고른다. (1 ≤ B ≤ A ≤ 500) 그 다음, 선영이는 상근이가 고른 수를 맞춰야 한다.상근이는 선영이에게 다음과 같은 힌트를 주었다.A의 제곱은 B의 제곱보다 N만큼 커 (1 ≤ N ≤ 1,000)위의 힌트 조건을 만족하는 A와 B 쌍의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다.출력상근이의 힌트 조건을 만족하는 (A,B) 쌍의 개수를 출력한다.풀이1 ≤  B ≤ A ≤ 500에 대해 A^2 - B^2 == N인 경우를 세어주자.만약 찾았다면, 이후의 차는 무조건 N보다 크다. 다음 B로 넘어가자. 소스코드보기출처https://www.acmicpc.net/problem/6131