Don't give up!

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

2166번: 다각형의 면적 (acmicpc.net) 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 3~10,000개의 점으로 이루어진 다각형은 각 꼭짓점을 이어 만든 1개 이상의 삼각형으로 표현할 수 있습니다. 따라서 0번째 점을 기준점으로 잡고 시계방향으로 겹치지 않는 삼각형의 너비를 모두 합한다면 다각형의 너비를 찾을 수 있다고 생각하였습니다. 코드 import java.io.*; import java.util.*; class Main { public static void main(String[]..

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..

1929번: 소수 구하기 (acmicpc.net) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 소수가 아닌 수는 소수로 나누어 떨어져야 합니다. 따라서 2부터 시작하여 소수를 찾고, 해당 값의 곱으로 나타내어지는 수들을 소수가 아닌 수라고 결정할 수 있으므로 이를 구현한다면 문제를 해결할 수 있을 것이라고 생각하였습니다. 코드 import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws IOE..

1022번: 소용돌이 예쁘게 출력하기 (acmicpc.net) 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 소용돌이는 가장 안쪽에서부터 n번째 테두리는 (2n-3)^2+1 ~ (2n-1)^2의 값을 갖습니다. 우측 테두리서부터 시작하여 +1이 진행되므로 상, 하, 좌, 우로 나누어 (a, b) 위치의 값을 식으로 나타낼 수 있다고 생각하였습니다. 코드 import java.io.*; import java.util.StringTokenizer; class Main { public static void main(String[] args) throws IOException { BufferedRea..