2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 읽기 아 역시 DP 문제는 쉽지 않다. 사실 그렇게 어려운 문제인 것 같지는 않지만.. 처음에 DFS로 했다가 2^1000이니까 당연히 시간초과가 나고, 거의 바로 아 DP인 것 같다는 생각을 했다. 그런데 처음에 N, K로 접근하지 않고, 첫 번째 원소를 선택하는 경우, 첫 번째 원소를 선택하지 않는 두 가지 경우를 생각했다. 즉, N, 2로 접근했다. 그런데 이렇게 하니 DP 배열에 경우의 수를 저장하는 게 아닌, 선택한 원소의 개수를 저장하게 되고 답을 제대로 구하지 못했다..

12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 문제 읽기 처음 문제를 읽고 예제를 한 번 그려봤다. 위와 같은 과정을 통해서 이루어진다면 돌이 정확히 분배된다. 위에서 알 수 있는 점은, 세 그룹에 있는 돌의 합이 3으로 나누어 떨어지지 않는다면 무조건 0을 출력한다는 점과, 이 문제는 다른 알고리즘 보다는 완전 탐색을 해야 할 것 같다는 느낌(?)이다. 그래서 완전 탐색인 DFS를 통해서 풀어보았다. 문제 풀기 처음 작성했던 풀이 과정은 크게 복잡하진 않았다. 우선 세 그룹을 두 그룹씩 개수를 비교해서..

3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 문제 읽기 일단 처음 딱 문제를 읽었을 때는.. 복잡하게 여러 연산이 있는 것처럼 나왔지만 결국엔 직사각형의 연결 컴포넌트 개수를 구하는 문제라는 생각이 들었다. 다음 그림을 보면 쉽게 이해할 수 있을 것이다. 그래서 이를 이용해서 문제를 해결했다. 문제 풀기 처음에 풀이 과정을 다음과 같이 구상했다. 다시 정리해 보면 다음과 같다. 사각형 좌표를 입력 받아 사각형 정보를 배열에 저장한다. 모든 사각형을 맵에 그려준다. 사각형을 그린다는 것은 맵에 각 방향에 대해 이동 가능..

11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 읽기 이 문제는 앞서 풀었던 세그먼트 트리를 활용한 문제이다. 구간 합 구하기와 크게 다를 건 없다. 세그먼트 트리를 이용하면 된다. 세그먼트 트리, Segment Tree 세그먼트 트리, Segment Tree ❓ 세그먼트 트리, Segment Tree 세그먼트(Segment)는 영어 뜻 자체로는 분할, 단편, 구분 등의 의미를 가진다. 이는 특정 구간 내 데이터에 대한 연산 또는 쿼리를 빠르게..

6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 읽기 확실히 어려웠다! 플레 문제는 역시 뭔가 다르다. 일단 처음에 이 문제를 봤을 때는 감이 전혀 오지 않았고, 일단 패스했었다. 입력 값이 너무 커서 엄두가 나지 않았다.. 그 당시에는 입력 값이 크면 DP?라는 생각밖에 없었기 때문에 풀지 못했다. 시간이 좀 지나고 다시 풀어봐야 겠다는 생각을 했고, 다시 봤지만, 역시나 잘 모르겠더라. 그래서 해당 알고리즘을 먼저 공부하고 해야겠다 싶어 알고리..

2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 읽기 이번 문제는 어떤 자료구조를 사용하는지 알고 푸는 것이기 때문에 어렵지 않았다. 세그먼트 트리 자료구조를 공부했고, 이를 적용하면 쉽게 해결할 수 있는 문제이다. 세그먼트 트리에 관한 자세한 설명은 다음 포스팅에서 알아볼 수 있다. 세그먼트 트리, Segment Tree 세그먼트 트리, Segment Tree ❓ 세그먼트 트리, Segment Tree 세그먼트(Segment)는 영어 뜻 자체로는 분할, 단편, 구분..