![]()
문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 시간초과에 많이 좌절했던 문제였다. 배낭문제랑 비슷해서 접근방법은 배낭문제랑 비슷하게 했다. 특이한 점은 가방마다 보석을 하나 담아야 하기 때문에 그 부분을 신경 써줬다. 우선 입력받은 보석을 정렬했다. 우선 무게 순으로 내림차순 정렬했다. 무게가 같다면 보석의 가치로 내림차순 정렬했다. 이유는 단위무게가 높더라도, 가벼..
![]()
문제 https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 문제 풀이 DP 문제로 판단하는 과정은 어렵진 않지만, 어떤 방법으로 풀어야 할지는 아직도 어려운 것 같다. Top-down으로 풀지, Bottom-up으로 풀지, 재귀를 호출할지 등등.. 나는 개인적으로 Bottom-up을선호한다. 해당 문제가 DP인 이유는 이전 선택지에 현재 선택지가 영향을 받기 때문이다. 대부분 나는 이런 문제라고 판단이 되면 DP라고..
![]()
문제 https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 문제 풀이 접근방법에 대해서 많은 고민을 했었다. 시간제한이 1초이고, 이닝의 최대수가 50이며, 순서를 결정해야 하는 타자의 명수는 8명이었다. 그렇다면 시간복잡도는 50*8!*@인데, 시간복잡도가 1초는 안넘길거 같아서 타자의 대한 모든 경우의 수를 계산해도 문제가 되지 않을것이라고 판단했다. 8P3인 이유는 4번 타자는 첫번째 선수로 결정되었기 때문이다. 순열에 대한 코드는 정말 간단하다. ..
![]()
문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 문제 풀이 모든 좌표에 대해서 종이를 계속 바꿔가면서 붙이고, 최소한의 종이 개수를 구하면 될 것이라고 판단했다. 이유는 배열의 크기가 그렇게 크지 않다. 10*10이므로 n^2이더라도 넉넉하다고 생각했다. 종이의 종류가 많지 않다. 즉 하나의 좌표에서 종이의 종류대로 붙여가면서 확인을 하더라도 크게 시간이 오래 걸리지 않을 것 같았다. 따라서 나는 종이가 들어갈 수 있는 좌표에 대..
![]()
문제 https://www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 문제 풀이 배열 돌리기 2의 상위 문제다. 총 6가지의 연산이 있는데, 1번과 2번은 각각 상하반전과 좌우 반전이다. 1번과 2번은 각각 가운데 행을 기준으로 끝과 끝을 바꿔주면 된다. 3번과 4번은 반시계와 시계방향으로 90도 회전하는 것이다. 여기서 중요한 점은 시계방향으로 한번 돌릴 때마다 N과 M이 바뀐다는 ..
![]()
문제 https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 문제 풀이 정말 싫어하는 문제의 부류이다.. 배열 회전, 뒤집기 같이 수학과 같이 사용해야 하는 문제는 정말 까다로운 것 같다. 해당 문제의 특이점은 배열 전체를 회전시키는것이회전시키는 것이 아닌 각 인덱스의 원소들을 회전시키는 것이다. 통째로 회전하는 것과 소용돌이처럼 회전시키는 것은 아예 다른 ..
![]()
문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 풀이 접근 방법에 대해서 많은 고민을 했다. 우선 지역구를 나누는 방법에 대해서 고민을 했는데, 조합을 써서 A와 B 지역구를 나누기 브루트포스로 나누기 두 방법 모두 하나의 지역을 정하면 나머지 구역의 지역을 결정 지을 수 있다. 브루트포스보단 코드적으로 깔끔한 조합을 사용해서 구역을 나눴다. 구역을 나눴다면 이젠 나눈 구역의 지역들이 연결되어 있는지를 확인해야한다. 여러 방법이 있지만 나는 BFS를 이용..
![]()
문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 풀이 처음에 N개의 행성을 받아서 Prim 알고리즘을 사용해서 구현했었다. 그렇게 하다보니 메모리초과가 발생했다. 도저히 이유를 알지 못해서 질문게시판을 참고했다. 정점의 개수가 N개고, 최대 입력개수가 100,000개인데 모든 행성간의 간선 정보를 포문으로 계산할 시 메모리 초과가 발생하는것이었고, 메모리초과를 해결하기 위해서 간선을 최적화해서 수를 줄..
![]()
문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 전형적인 그래프 탐색 문제이고, 그래프 내에서 구역을 그룹핑하는 문제이다. 문제에서 요구하는 바는 하나의 그래프를 두 가지 방식으로 그룹핑하는것이다. RGB 각각의 컬러를 구별할 수 있는 영역(적록색약 X) RGB 중 R과 G를 하나의 영역으로 처리하는 영역(적록색약 O) 여러 가지 방식이 있겠지만, 두 번의 탐색을 통해서 각 영역을 구별했다. public static bo..
