문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 O(nlogn) 안에 풀어야 하는 문제이다. nlogn으로 풀어야 하기에 이진 탐색을 추가했다. 가장 먼저 수열이 담긴 배열을 seq이라 하고, dp 배열을 만들어주는데 dp[i]의 경우에는 i의 길이의 증가하는 수열의 가장 끝의 값이 담겨있다. 코드 import java.io.BufferedReader import java.io.BufferedWriter import java.io...
문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 투 포인터 문제입니다. 3개의 용액의 합의 절대값이 0과 가장 가까운 3개의 용액을 찾는 문제입니다. 3개의 용액을 구하기 위해, 기준이 되는 용액을 하나를 고정하고, 두 용액을 투포인터를 통해 포인터를 이동하며, 최적의 합을 찾는 것이 핵심입니다. for문을 통해 모든 용액을 기준으로 합니다. 이 때 for문의 범위를 전범위로 하는 것이 아니라, 두가지 용액이 더..
문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 문제의 조건을 보면, 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 두 가지 조건이 있습니다. 두번째 조건을 보면, 최소 신장 트리를 찾아내야 하는 문제입니다. 그리고 가중치의 경우에는 첫번째 조건을 통해 알 수 있습니다. 곧 두 별 사이의 거리가 가중치입니다. 최소 신장 트리를 구하는 방법..
문제 https://www.acmicpc.net/status?user_id=smc3843&problem_id=9466&from_mine=1 채점 현황 www.acmicpc.net 풀이 dfs를 이용해 방문한 학생이 아니면 다음 학생으로 이동한다. 이미 방문한 학생이면, 사이클이 형성되었다는 뜻이다. 하지만, 이미 사이클이 형성이 되어 조를 이루었다면, 이미 계산한 값이므로 조를 이루지 않는 경우에만 전체 학생수에서 사이클 수 만큼 반복하여 제거해준다. 결국 구하는 정답이 팀을 이루지 못한 학생이므로, 초기 ans 값을 학생 수로 설정하여 팀을 이룬 학생을 빼주면 된다. 코드 import java.io.BufferedReader import java.io.BufferedWriter import java.i..
문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 구현 + 백트래킹으로 해결하는 문제이다. 가장 먼저 봐야할 문제의 조건이 있다. 움직이는 방향은 (상 , 하 , 좌, 우) 총 4개의 방향이며, 이동하는 방향에서 가장 앞에 있는 순으로 합쳐진다. 예를 들어 왼쪽으로 이동시 [2,2,2,0] 인 경우 [4,2,0,0] 으로 바뀌게 된다. 4개의 방향을 각각 구현해주어야 하는데, 큰 틀로 보면, 새로운 배열을 ..
문제 https://www.acmicpc.net/problem/27172 풀이 그냥 단순하게 모든 플레이어 간의 대결을 모두 구하여 풀게 된다면 100000! 로 구할 수 없는 문제이다. 그렇다면, 다르게 풀어야 하는데 에라토스테네스의 체를 이용하여 해당 숫자의 배수를 카드 목록에 가지고있다면 , 결투를 하게 진행하면 된다. 숫자가 담긴 카드 배열을 card라고 하고, 숫자를 가지고 있는지 확인하는 배열을 has라고 했을 때, card[i] 부터 card[N]까지 배수를 찾아, 가지고 있는 카드인지 확인하여 점수를 계산해주면 된다. 코드 import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader i..
