전체 글667 [백준] 17386번 - 선분 교차 1 [Java] https://www.acmicpc.net/problem/17386 1. 아이디어 두 선분의 교차 여부는 CCW 알고리즘으로 구할 수 있다.2. 문제풀이 세 점이 일직선 위에 있는 경우가 없으므로 L1에서 L2의 두 점에 대한 외적 벡터의 방향이 다르고, L2에서 L1의 두 점에 대한 외적 벡터의 방향이 다르면 두 선분이 교차한다는 점을 이용해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syst.. 2024. 12. 5. [백준] 14215번 - 세 막대 [Java] https://www.acmicpc.net/problem/14215 1. 아이디어 삼각형을 만드려면 가장 긴변이 나머지 두변의 길이의 합 보다 짧아야 한다는 점을 활용했다.2. 문제풀이 막대의 길이를 줄일 수만 있으므로 짧은 두 막대는 그대로 두고 가장 긴 막대의 길이가 나머지 두 막대의 길이의 합보다 짧으면 그냥 사용하고 길면 두 막대의 길이의 합 -1 로 줄이는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputS.. 2024. 12. 5. [백준] 1064번 - 평행사변형 [Java] https://www.acmicpc.net/problem/1064 1. 아이디어 삼각형을 만들 수 있는지 여부는 CCW 알고리즘을 활용해서 구했고, 평행사변형 둘레의 길이의 차의 최댓값은 기존 삼각형의 각 변의 길이를 크기 순으로 a, b, c라고 했을 때, 가장 짧은 둘레의 길이는 2 * (a + b), 가장 긴 둘레의 길이는 2 * (b + c)라는 점을 이용했다.2. 문제풀이 세 점이 한 직선 위에 있으면 삼각형을 만들 수 없으므로 CCW의 값이 0인지 판단하는 방식으로 구현했다.둘레의 길이의 차는 위 수학적 테크닉으로 간단하게 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void mai.. 2024. 12. 5. [백준] 1027번 - 고층 건물 [Java] https://www.acmicpc.net/problem/1027 1. 아이디어 현재 빌딩에서 특정 빌딩이 보이는지 여부를 CCW 알고리즘을 통해 구한 외적 벡터의 방향으로 알 수 있다는 점을 이용했다.2. 문제풀이 현재 빌딩의 지붕에서 특정 빌딩의 지붕이 보이는지 판단할 때 기준점에 대해 CCW를 통해 방향이 양의 값이면 보이는 빌딩이고 0이면 접하는 빌딩, 음이면 기준점에 가려진 빌딩이라는 점을 이용했다. 기준점은 현재 빌딩에 대해 빌딩의 바닥을 기준으로 하고 보이는 빌딩을 찾으면 해당 빌딩의 지붕으로 옮겨준다.보이는 빌딩에 대해 나중에 해당 빌딩에서 현재 빌딩을 비교할 때도 당연히 보이는 빌딩으로 판단하기 때문에 한번 확인하면 양쪽 모두 보이는 빌딩으로 체크를 해주고, 대신 현재 빌딩에서 오른쪽에.. 2024. 12. 5. [백준] 11758번 - CCW [Java] https://www.acmicpc.net/problem/11758 1. 아이디어 CCW 알고리즘을 구현만 하면 되는 문제로 벡터의 외적을 구하는 ccw 메서드를 작성해서 구현했다.2. 문제풀이 외적 벡터를 구한 이후 -1, 0, 1로 출력하기 위해 삼항 연산자와 절댓값을 구할 수 있는 Math.abs를 활용했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTo.. 2024. 12. 5. [백준] 3009번 - 네 번째 점 [Java] https://www.acmicpc.net/problem/3009 1. 아이디어 나머지 하나의 점의 좌표는 기존에 주어진 점 3개 중 한번만 등장한 좌표의 조합이 된다는 점을 활용했다.2. 문제풀이 주어진 3개의 x좌표, 3개의 y좌표를 각각 배열에 저장한 후 정렬을 해줬다.이후 배열의 가운데 원소와 앞 원소를 비교해서 다르면 앞 원소가 한번만 등장한 것이고 같으면 뒷 원소가 한번만 등장한 것이므로 간단하게 해결할 수 있었다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new B.. 2024. 12. 5. [백준] 1085번 - 직사각형에서 탈출 [Java] https://www.acmicpc.net/problem/1085 1. 아이디어 직사각형 각 변까지의 거리 중 최솟값을 찾는 문제로 좌우 이동에 대한 최솟값과 상하 이동에 대한 최솟값을 구해서 최종 최솟값을 구하는 방식으로 구현했다.2. 문제풀이 경계까지 가는 최솟값은 쭉 한 방향으로 가는 것이므로 4가지 경우만 따지면 된다.Math.min 메서드를 이용해서 한 줄로 간단하게 풀이했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input.. 2024. 12. 5. [백준] 14681번 - 사분면 고르기 [Java] https://www.acmicpc.net/problem/14681 1. 아이디어 좌표의 부호로 사분면을 구분할 수 있다는 점을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 x좌표와 y좌표의 부호에 맞게 조건문 분기처리를 해서 해결했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int x = Integer.parseInt(br.readLine()); int y = Integer.parse.. 2024. 12. 5. [백준] 10610번 - 30 [Java] https://www.acmicpc.net/problem/10610 1. 아이디어 30의 배수는 3의 배수면서 10의 배수라는 점을 활용하면 간단하게 해결할 수 있다.3의 배수는 각 자릿수의 합이 3의 배수가 되고 10의 배수는 1의 자릿수가 0이라는 특징이 있는데 이 두가지를 모두 만족하면 30의 배수가 된다.2. 문제풀이 각 자릿수를 저장하는 배열 nums, 0을 포함했는지 판단하는 변수 hasZero, 각 자릿수의 합을 저장하는 변수 sum을 선언하고 입력에 맞게 초기화해준다.이후 0을 포함하면서 각 자릿수의 합이 3의 배수면 재배치로 30의 배수가 될 수 있으므로 nums를 정렬한 이후 역순으로 순회하며 가장 큰 수를 구해주고 30의 배수가 아니면 -1을 출력하는 방식으로 구현했다.3. 코드 i.. 2024. 12. 4. [백준] 10250번 - ACM 호텔 [Java] https://www.acmicpc.net/problem/10250 1. 아이디어 문제 설명이 약간 어려운데 간단하게 101, 201, 301, 401, ..., 102, 202 이렇게 채워나가면 된다.한칸씩 이동하며 찾아도 되지만 몫과 나머지의 특성을 잘 활용하면 O(1)로 구할 수 있다.2. 문제풀이 N번째 손님에 대해 층은 N % H, 방은 N / H 로 계산할 수 있다.손님과 층, 방 모두 1번부터 시작하므로 보정으로 N을 N - 1, 층을 N % H + 1, 방을 N / H + 1로 바꾸면 답을 구할 수 있고 방은 10호 보다 작을 때는 앞에 0을 붙여야 하는 점만 조건문으로 처리하면 된다.3. 코드 import java.io.*;import java.util.*;public class Mai.. 2024. 12. 4. [백준] 15965번 - K번째 소수 [Java] https://www.acmicpc.net/problem/15965 1. 아이디어 에라토스테네스의 체로 소수 리스트를 미리 구하고 인덱스로 찾는 방식으로 구현했다.자연수가 최대 500,000으로 주어졌는데, 50만번째 소수가 1000만 이하 범위에 있는 점으로 좀 더 간편하게 구현했다.2. 문제풀이 에라토스테네스의 체로 소수 여부를 먼저 판정을 하고 해당 결과로 소수 리스트를 구했다.K번째 소수는 소수 리스트에서 K-1 인덱스에 위치한다는 점을 이용하면 간단하게 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 12. 4. [백준] 1735번 - 분수 합 [Java] https://www.acmicpc.net/problem/1735 1. 아이디어 두 분수의 합을 기약분수로 만드려면 통분 이후 유클리드 호제법으로 약분을 하면 간단하게 해결할 수 있다.2. 문제풀이 통분으로 두 분수의 덧셈을 먼저 해주고 분자, 분모의 최대 공약수로 분자, 분모를 나눠주는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWrit.. 2024. 12. 4. 이전 1 ··· 50 51 52 53 54 55 56 다음
