Don't give up!

2156번: 포도주 시식 (acmicpc.net) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 연속해서 3잔을 마실 수 없는 조건 하에서 최대한 마실 수 있는 양을 계산하기 위해 다음의 케이스를 생각하였습니다. 이번에 마시지 않음 이전 잔을 마시지 않았고 이번에 마심 이전 잔을 마셨고 이번에도 마심 이번 잔을 마시지 않는 케이스에서는 이전 잔에서 마신 것이 문제가 되지 않으므로 이전 잔의 3가지 케이스의 결과를 비교하여 최대값을 선택하고, 2 ~ 3번째 케이스에 대해서는 이..

11286번: 절댓값 힙 (acmicpc.net) 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 절대값이 가장 작은 값을 출력하고, 절대 값이 가장 작은 값이 여러 개 있을 경우 가장 작은 값을 출력해야 합니다. 0이 입력으로 주어질 때마다 출력을 수행해야 하므로 각 입력에 대해 절댓값과 실제 값을 미리 저장한 후 두 값의 비교를 통해 우선순위를 결정하는 것이 중요하다고 생각하였습니다. 코드 import java.io.*; import java.util...

1655번: 가운데를 말해요 (acmicpc.net) 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 최대 100,000 크기의 N에 대해 중간 값을 빠르게 구하기 위해서는 단순 탐색보다 빠른 탐색이 필요합니다. 중간 값이 대체될 경우 중간 값보다 작은 값들 중 최대 값과 큰 값들 중 최소 값 중 하나로 대체될 것입니다. 따라서 중간 값, 보다 작은 값들의 집합, 보다 큰 값들의 집합으로 나눔으로써 빠르게 중간 값을 구할 수 있을 것이라고 생각하였습니다. 코드..

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일 경우 한 직선에 위치함을 의미하므로 외적의 결과 값만으로도 원하는 결..