반응형 재귀2 [백준/C++] 기말고사 작품전시 (No. 28094) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 작품마다 순서가 있어서 어떤 작품A가 작품 B보다 앞에 있는 경우 점수 V를 얻는 문제다. 여기서 A작품이 B작품이 앞에 있을 경우만 점수 V를 얻으므로, 두 작품을 비교하는 경우를 2차원 vector에 저장해 두고 작품의 순서가 정해지면, 순서가 vector[A][B]의 값을 구하면 된다. 그림을 통해 생각해 보면vector[A][B]는 A가 B보다 앞에 있는 경우 얻는 점수의 총 합이다. 그리고 점수를 얻는 경우 중 최대값을 구하고, 그 최대값을 얻는 경우가 총 몇 개인지 출력하면 된다. 모든 경우의 수는.. 2024. 6. 15. [프로그래머스/C++] 유사 칸토어 비트열 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제에서 나오는 수열은 프랙탈 구조처럼 일정한 규칙을 갖고있는 수열이다. 만약 이 문제에서 1의 개수를 직접 count한다면 최대 개수가 5^20 이기 때문에 시간복잡도에서 문제가 생길 수 있다. 그러므로 규칙을 이용해 1의 개수를 직접 세지 않고, 범위를 이용해 빠르게 풀었다. 일단 l ~ r까지 1의 개수를 구하기 위해 생각해 볼 것은 n = i 인 경우의 모든 1의 개수와 n = i -1 인 경우의 모든 1의 개수는 총 4배 차이가 난다. 왜냐하면 이전 배열의 1이 11011로 바뀌고 0은 00000으로 바뀐다. 그러므로 1의 개수는 이전의 1의 개수에만 영향을 받아 4배씩 증가하는 것이다. 그리고 [l.. 2024. 4. 20. 이전 1 다음 반응형
