전체 글
백준 2609 - 최대공약수와 최소공배수
https://www.acmicpc.net/problem/2609 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)); StringTokenizer st = new StringTokenizer(br.readLine()); int a=stoi(st.nextToken()); int b=stoi(s..
백준 22857 - 가장 긴 짝수 연속한 부분 수열(small)
https://www.acmicpc.net/problem/22857 1. 유형 - 투포인터 2. 풀이 - 투포인터 변수 R, L을 잡는다. 시작 인덱스는 0번 - R, L의 사이에 홀수의 갯수가 K개 초과면 L증가, 반대는 R증가 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)); StringTokenizer st = new StringTokenizer(br.readLine()); int N =stoi(st..
[백준 18311] 왕복
https://www.acmicpc.net/problem/18311 18311번: 왕복 첫째 줄에 정수 N, K가 공백을 기준으로 구분되어 주어진다. (1≤N≤100,000) 단, K는 항상 왕복 거리보다 작은 양의 정수 혹은 0으로 주어진다. 둘째 줄에 1번부터 N번까지 각 코스의 길이가 공백을 www.acmicpc.net 1. 유형 구현 2. 풀이 반복문을 돌면서 K에서 입력값을 뺴준다. 가는 경우, 오는 경우를 나눠서 생각. 0미만인 경우 index+1을 출력 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedRea..
[백준] 1446 지름길
https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 1. 유형 완전탐색, 다익스트라 2. 풀이 첫번째 풀이, 완전탐색 총 12개의 값만 주어지기 때문에 완전탐색으로 충분히 구할 수 있다. 1. 시작, 도착지 기준으로 정렬 2. 선택을 하는 경우, 안 하는 경우로 나누어 모든 경우 탐색 import java.io.*; import java.util.*; public class Main { static List list; static int..
[백준 1251] 단어 나누기
https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 1. 유형 브루트포스 2. 풀이 문자열 최대 길이가 50이고, 자를 두 곳을 선택해야한다 그럼 문제를 50개 중에서 2개를 선택으로 바꿔서 풀면 쉽다. 1. 전역 탐색으로 숫자 2개를 선택 2. 뒤집고 전부 합친다 3. 정렬한다 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[]..
[백준 9996] 한국이 그리울 땐 서버에 접속하지
https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 1. 유형 문자열 2. 풀이 1. 별표 기준으로 좌우 나누기 2-1 좌우길이가 비교문자열의 초과인 경우 NE 2-2. 이하인 경우 앞뒤 비교 3-1. 좌우가 비교 문자열과 일치하면 DA 3-2. 불일치하면 NE 3. 코드 import java.io.*; import java.util.*; public class Main { public static void mai..
백준 16439 - 치킨치킨치킨
[문제 바로가기] 1. 유형 브루트포스 2. 풀이 1. M까지의 수 중에서 3개를 조합을 선택 2. 각 경우의 수 마다 최대값 구함 3. 코드 import java.io.*; import java.util.*; public class BOJ_16439_치킨치킨치킨 { static int N, M, ans; static int arr[][]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N=stoi(st.nextT..
백준 16439 - 치킨치킨치킨
[문제 바로가기] 1. 유형 이분탐색 2. 풀이 문제를 파악하고 이분탐색을 생각할 수 있어야하는 문제였습니다. 구현 난이도는 기본적인 이분탐색만 할 수 있으면 가능한 문제였습니다. 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)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = stoi(st..
백준 15970 - 화살표 그리기
[문제 바로가기] 1. 유형 정렬, 브루트포스 2. 풀이 점의 범위가 100000이기 때문에 O(N^2)이면 시간초과입니다. 따라서 동적프로그래밍을 썼습니다. 설계 1) 위치 순서대로 입력값 정렬 2) 색깔별로 큐 배열 만들고, 같은 색 끼리 큐에 삽입(굳이 큐를 사용안하고 배열 사용해도 됨) 3) 같은 색 끼리의 위치를 빼서 DP에 최소값 저장 예제1을 기준으로 설명하면, 색깔1의 위치는 0, 3, 5 순서로 입력됩니다. 0과 3의 차이는 3이고, DP[0]=3, DP[3]=3 을 입력. 3과 5의 차이는 2이고, DP[3]=2 (기존 값이 3이었는데, 2가 더 작으므로 초기화), DP[5]=2 위 과정을 색깔별로 해주면 됩니다. 3. 코드 import java.io.*; import java.util..
백준 16987 - 계란으로 계란치기
[문제 바로가기] 1. 유형 브루트포스 DFS 백트래킹 2. 풀이 DFS를 쓰는 문제였습니다. 처음에 한글 이해하는게 조금 힘들었습니다. 2-1. 설계 2-2. 코드 풀이 3. 코드 import java.io.*; import java.util.*; public class Main { static int N, answer; static int arr[][]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = s..