목록2024/08/29 (1)
tlov
1463 - 1로 만들기
문제: boj.kr/1463날짜: 08/29 (목)성공여부: O (00:37:07) 실버3의 DP 문제이다. x가 3으로 나누어 떨어지면 3으로 나눈다.x가 2로 나누어 떨어지면 2로 나눈다.1을 뺀다. 정수 x에 대해서 적용할 수 있는 3가지 연산인데, 뭔가 연산의 순서가 있는 것처럼 보여서 순서를 지켜서 풀려고 하면 틀린다. 위의 3가지 연산은 3가지 경우의 수이고 정수 x에 대해서 각각 모두 적용시켜서 모든 경우의 수를 찾아서 푸는 문제이다. 라는 생각을 가지고 완탐으로 풀 수 있을까? 라고 생각해보아야 한다. 그럼 시간 복잡도는 100만개의 숫자에 대해서 3개의 연산을 하므로 3^100임을 알 수 있다. 근데 문제에서 주어진 시간이 0.15초이므로 무조건 시간 초과가 날 것이다.. 그럼 어떻게 풀..
알고리즘 문제
2024. 8. 29. 16:16