PS/Problems (49) 썸네일형 리스트형 [Java] 백준 10999번 합 구하기 - Lazy Segment Tree https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net import java.util.*; import java.io.*; public class p5_10999 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static int n, m; static long.. [Java] 백준 2098번 외판원 순회 - TSP, 비트필드 DP https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net - 현재까지 방문한 도시 번호에 대한 정보를 비트마스킹 (visit) - wei는 a 도시에서 b도시로 갈 때의 거리 dp는 visit 상황에서 now 도시에 있을 때 목적지까지 가질 수 있는 최소 거리값 - 모든 도시를 방문하는 사이클이 단 1개 생기기 때문에 어느 도시를 시작점으로 잡아도 답은 같다. ==> 0번 도시를 시작점으로 잡아도 된다! 처음에는 N.. [Java] 백준 17387번 선분 교차 2 - CCW https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 한 문제 푸느라 반나절이 날아갔다... 처음에는 수학적으로 접근하려 했는데 double을 쓰다보니 범위를 감당할 수 없어져서 CCW 알고리즘임을 알았다. case work에 실수가 많아서 시간이 많이 들었다. import java.util.*; import java.io.*; public class g2_17387 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWr.. [Java] 백준 12094번 2048 (Hard) - 빡구현 https://www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 12100번 2048(Easy)와 유사하지만 수행이 5번인 easy와 다르게 10번이나 되어서 빡센 가지치기가 필요했다. 3시간 걸림; import java.util.*; import java.io.*; public class p4_12094 { static FastScanner fs = new FastScanner(); static PrintWriter pw = ne.. [Java] 백준 2623번 음악프로그램 - 위상 정렬 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net import java.util.*; import java.io.*; public class g2_2623 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static int n, m; static List list = new ArrayList(); st.. [Java] 백준 1062번 가르침 - 비트마스킹 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net a~z의 26개 문자의 포함 여부를 32비트뿐인 int에 비트마스크로 저장가능하다. 가르쳤는지 여부도 check에 비트마스킹 때렸다 import java.util.*; import java.io.*; public class g4_1062 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(S.. [Java] 백준 9466번 텀 프로젝트 - DP, case work https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 처음에는 사이클에 구성되지 않는 노드의 개수를 찾는 문제라고 생각했으나 시간복잡도가 n^2가 되어 불가능했기에, 어느 노드에서 출발하더라도 마지막에는 항상 사이클로 연결된다는 점을 이용했다. import java.util.*; import java.io.*; public class g3_9466 { static FastScanner fs = new FastScanner(); static PrintWri.. [Java] 백준 7579번 앱 - 배낭 문제 응용 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 배낭 문제의 응용편이다. 기존 문제는 (무게 제한 안넘기기 -> 가치 최대화) 였다면 (메모리 제한 넘기기 -> 코스트 최소화) 여서 발상이 쉽지 않았다. import java.util.*; import java.io.*; public class g3_7579 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWri.. 이전 1 2 3 4 5 ··· 7 다음