= 접근 과정 ( 틀림 ) = 이렇게 N개의 전구와, K가지의 색 => 최대 200개의 전구, 최대 20개의 색이므로 완전 탐색을 이용하면 시간 초과로 분명히 오답! => O(N!), 이유는 N개의 색이 모두 다 다를 수 있기 때문 이러한 문제는 DP를 이용해서 시간을 줄이는게 핵심이다. 처음 나는 재귀 함수를 이용해서, 이미 거친 전구들은 return하는 형식으로 문제를 접근했다. 1. int[] arr = new int[n] 배열에 1, 1, 2, 3, 3, 3, 2, 2, 1, 1의 값을 넣고 0번 index의 값을 2로 바꿨을 때, 인접한 값(1번 index)이 0번째 값(1)이랑 같을 때 같이 2로 변경해주고 아니면 return을 하는 형식으로 count를 했다. 2. 모든 값이 k로 다 통일 ..
= 내 접근 방법 ( 오답 ) = 흔히 사용하던 2중 for문을 사용했기 때문에 오답이다. 투 포인터 알고리즘은 언제 사용해야 될까? 문제를 잘 봐야한다. 시간 제한은 1초, n은 1000000이기 때문에 2중 for문을 이용한 단순한 코드는 O(N^2)이기 때문에 시간을 초과한다. 이러한 문제에 닥쳤을 때 투 포인터 알고리즘을 이용해서 해결해야 됨! https://byungil.tistory.com/193 이 링크에서 알고리즘에 대한 설명을 써놨다. = 알고리즘을 이용한 접근 ( 정답 ) = 1. 정렬된 배열이 필요. 2. 왼쪽 맨끝 과 오른쪽 맨끝에서 순차적으로 번갈아 가면서 접근 만족 => end-- or start++ 둘 중 하나, count++ 두 수의 합이 더 크면 end-- 두 수의 합이 더..
문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 예제 입력 1 복사 216 예제 출력 1 복사 198 = 오답 코드 = 처음에 내 코드에 오..
= 문제 = 문제 KOI 전자에서는 건강에 좋고 맛있는 훈제오리구이 요리를 간편하게 만드는 인공지능 오븐을 개발하려고 한다. 인공지능 오븐을 사용하는 방법은 적당한 양의 오리 훈제 재료를 인공지능 오븐에 넣으면 된다. 그러면 인공지능 오븐은 오븐구이가 끝나는 시간을 분 단위로 자동적으로 계산한다. 또한, KOI 전자의 인공지능 오븐 앞면에는 사용자에게 훈제오리구이 요리가 끝나는 시각을 알려 주는 디지털 시계가 있다. 훈제오리구이를 시작하는 시각과 오븐구이를 하는 데 필요한 시간이 분단위로 주어졌을 때, 오븐구이가 끝나는 시각을 계산하는 프로그램을 작성하시오. 입력 첫째 줄에는 현재 시각이 나온다. 현재 시각은 시 A (0 ≤ A ≤ 23) 와 분 B (0 ≤ B ≤ 59)가 정수로 빈칸을 사이에 두고 순..
