[백준(baekjoon) 9095] 1, 2, 3 더하기 문제 백준 9095 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 예시 n = 4; 1+1+1+1 / 1+1+2 / 1+2+1 / 2+1+1 / 2+2 / 1+3 / 3+1 input 첫째줄 : T(테스트 개수) 그 다음 줄 부터 : n(11보다 작은 자연수, T번 반복됨) 해결 우리가 찾고자 하는 수는 1, 2, 3의 조합이다. 즉, 쉽게 생각해 1, 2, 3으로 각각 시작하는 경우의 수를 모두 찾아보면 답이 나온다. 예를 들어 n = 6라고 할 때, 1, 2, 3 을 기준으로 생각해 본다면, 6 = 1 + 5, 6 = 2 + 4, 6 = 3 + 3로 나타낼 수 있다. 즉 n = 6의 경우,..

문제 백준 11726 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 주의 할 것은 출력이 10007을 나눈 나머지 라는 것..! (이거 안 읽고 계속 틀렸었다…. 문제는 제대로 읽어야 한다..) 해결 처음에는 width 2인 정사각형이 몇 개가 들어가는 지에 따라 경우의 수를 나누어 보았는데, 결과적으로 더 쉬운 패턴을 발견할 수 있었다…. 1.n = 1 : answer = 1 2.n = 2 : answer = 2 3.n = 3 : answer = 결론적으로, 이러한 점화식 형태를 보인다. 그러니 우린 간단하게 점화식을 풀면 됨..! 알고리즘 DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다. 모두 알테지만, 다시 한번 간..

문제 백준 1463 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오. 해결 문제가 쉬운 편이지만, 자주 쓰이는 간단한 원리이니만큼 정리를 해보고, memorization 유무에 따른 시간 비교를 해보았다. 알고리즘 BFS 방식으로 해보았다. 트리 구조로 정리하자면 아래와 같다. Queue를 만들어 입력값을 우선 넣는다.(시작점) Queue안의 원소들은 하나씩 pop되어 문제에 정의된 1~3번 과정을 거쳐 Queue에 삽입된다. 일단 가능한 경우의 수를 모두 넣어..

문제 백준2018 1

[백준(baekjoon) 6064] (최대공약수/규칙 찾기) 카잉 달력 문제 백준 6064 M, N, X, Y가 주어질 때 가 몇 번째 해인지 구하여라. 단, 답이 존재 하지 않는 다면 -1 1

[백준(baekjoon) 2609] 최대공약수, 최소공배수(GCD/LCM) 원리/코드/유클리드 호제법 문제 백준 2609 최대공약수(GCD) 와 최소공배수(LCM) 를 구하시오. 원리 최대공약수 : 유클리드 호제법 사용 최소공배수 : 최대공약수 활용 유클리드 호제법 GCD(A, B) = A, B의 최대공약수 r = A % B 일 때, GCD(A, B) = GCD(B, r)이다. 단, r == 0이면 GCD(B, r) = B이다. 딱 r = A % B = 0으로, 딱 나누어 떨어지므로 최대공약수는 B 예시 A = 24, B = 82 GCD(24, 82) r = 24 % 82 = 24 r > 0 -> GCD(82, 24)호출 GCD(82, 24) r = 82 % 24 = 10 r > 0 -> GCD(24, ..