Don't give up!

12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 주어진 수열에서 부분 수열의 원소들이 인덱스가 증가함에 따라 값도 증가함을 만족한다면 증가하는 부분 수열이 될 수 있습니다. 첫번째 인덱스부터 탐색을 시작하여 부분 수열을 형성하고, 마지막 원소보다 작은 값이 발견되었을 경우 부분 수열을 새로 형성하거나, 해당 원소를 무시하고 다음 원소를 탐색하여 부분 수열에 추가함으로써 가장 긴 증가하는 부분 수열을 찾을 수..

1300번: K번째 수 (acmicpc.net) 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? NxN 배열의 각 원소가 갖는 값은 행 또는 열의 배수로 지정되어 있습니다. 따라서 각 행에서 x보다 작은 값의 개수는 x/i와 N 중에서 작은 값으로 구할 수 있습니다. (x값이 ixN보다 큰 값을 갖는 경우가 존재함) 따라서 B[k]는 x보다 작거나 같은 값을 갖는 원소의 수가 k개 이상인 x를 찾음으로써 답을 구할 수 있을 것이라고 생각하였습니다..

10830번: 행렬 제곱 (acmicpc.net) 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? NxN 행렬 A의 B제곱은 x1+x2+....=B를 만족하는 A의 xi제곱들을 곱하여 나타낼 수 있습니다. 이때 xi의 값들이 2의 제곱으로 나타내어질 수 있도록 한다면 A의 제곱, 4제곱, 8제곱을 구하여 결과를 빠르게 구할 수 있습니다. 이러한 xi 값들은 B를 2진수로 표현하여 1을 갖는 자리를 확인함으로써 빠르게 찾아낼 수 있을 것이라고 생각하였습니다. 코드 import java.io.*..

1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? +와 -만으로 이루어진 식에서 최소 값은 - 연산이 나온 이후의 값을 모두 -로 만들었을 때 구할 수 있습니다. 따라서 문자열의 첫 - 연산 위치를 확인하고, 문자열을 나눈 후 각 문자열의 숫자 값을 모두 합하여 첫 문자열로부터 도출한 값 - 나중 문자열로부터 도출한 값으로 문제를 해결할 수 있을 것이라고 생각하였습니다. 코드 import java.io.*; import ..

11758번: CCW (acmicpc.net) 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? P1과 P2, P2와 P3로 이어지는 선분이 시계 방향인지, 반시계 방향인지 확인하기 위해서 외적을 사용하고자 하였습니다. 두 직선을 외적하여 얻은 직선의 z방향이 + 값을 갖는다면 반시계, - 값을 갖는다면 시계방향을 의미합니다. 또한 z값이 0일 경우 한 직선에 위치함을 의미하므로 외적의 결과 값만으로도 원하는 결..

1931번: 회의실 배정 (acmicpc.net) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 한 회의실에서 진행 가능한 최대 회의의 수는 시작시간이 빠르고, 종료시간이 빠른 순으로 회의를 선택하는 경우입니다. 따라서 N개의 회의 정보를 종료시간과 시작시간에 따라 정렬한다면 문제를 해결할 수 있을 것이라고 생각하였습니다. 코드 import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedR..

1043번: 거짓말 (acmicpc.net) 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 진실을 아는 사람과 같은 파티에 속한 사람은 진실을 아는 사람이 됩니다. 결과적으로 과장된 이야기를 할 수 있는 파티를 찾기 위해서는 진실을 아는 사람들과 같은 파티에 참여하지 않아야 합니다. BFS로 진실을 아는 사람들이 참여하는 파티를 순회하며 다른 사람들을 queue에 넣음으로써 진실을 아는 파티와 그렇지 않은 파티를 계산할 수 있을 것이라고 생각하였습니다. 코드 import java.io..

2206번: 벽 부수고 이동하기 (acmicpc.net) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? (1,1)부터 (N,M)까지의 최단 경로를 구하기 위해서는 BFS를 사용하여 문제를 해결할 수 있을 것이라고 생각하였습니다. 문제에서 단 한번 벽을 부술 수 있다는 것을 고려해야 하는데, 이를 해결하기 위해서 벽을 부순 상태에서의 최단거리와 벽을 부수지 않은 상태에서의 최단거리를 별도로 계산하여 해결하고자 하였습니다. 코드 import java.i..