본문 바로가기

알고리즘/백준

 (51)
[백준] 1450 냅색문제 문제링크: www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 냅색문제랑 상관 없는 문제다. 속았다. 풀이방법을 모르겠어서 문제 분류를 보니 투 포인터였다. 투포인터인 것을 알고도 어떻게 투 포인터로 풀리는지 몰랐다. 다른 사람풀이를 참고해보니 집합을 절반으로 나누는 풀이가 있었다. 한참을 보고서야 이해했다. import java.util.*; import java.io.*; public class Main { public static int n,c; pu..
[백준] 19238 스타트택시[JAVA] 문제링크: www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제를 보자마자 이전에 풀었던 삼성 유형 중 아기상어 문제가 떠올랐다. 일부 조건만 제외하면 똑같이 풀면 된다. 현재 위치에서, 가진 연료로 가장 가까운 손님(여럿 있다면 위쪽일수록, 왼쪽일수록)을 태울 수 있으면 태우고 이동한다. 이동하면 손님을 목적지로 이동한 걸의 2배만큼 연료가 충전되며, 이 과정을 모든 손님을 목적지까지 이동할 수 있으면 남은 연료를, ..
[백준] 9370 미확인도착지[JAVA] 문제링크: www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 처음 아이디어는 start(시작점)에서 양옆 다리 g,h로 가는 최단거리 + 다리길이 + 후보지로 가는 거리가 start(시작점)에서 후보지로 가는 최단거리보다 작거나 같은 경우인 후보지만 채택하는 방식이었다. 이렇게 할 경우 다익스트라를 최소 2번 사용하는 것 같은데, 오랫동안 틀리거나 런타임 에러의 원인을 찾지 못해서 다른 사람의 아이디어를 참고했다. 다리길이를 2배보다 1 작은 홀수로, 나..
[백준] 15681 트리와 쿼리 문제링크: www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 너무 많이 풀어본 유형이라 쉬웠다. 문제 설명이 아주 구체적이어서 그래프와 트리의 개념을 이해하기에 좋고, 그것을 실습 해보는 목적으로 풀기에 좋은 문제인 것 같다. import java.io.*; import java.util.*; public class Main { public static int N,R,Q; public static ..
[백준] 7579 앱 문제링크: www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 1년 전에 풀다가 실패했던 문제다. 다시 풀려고 했는데 나아진 게 없는지 잘 풀리지 않았다. 반성했다. 그때 답을 보고도, 제대로 이해하지 않고 넘어갔던 것 같다. 이번 기회에 차근차근 이해 해보려 했다. 또, 재귀 호출을 통한 메모이제이션 방법이 떠오르지 않아서 bottom-up 방식으로 풀었지만 검색해보니까 재귀로 해결한 코드가 있었다. bottom-up을 어려워 하는 내겐 좋은 공부가 됐다. 다음번엔 ..
[백준] 11066 파일 합치기 문제링크: gaegosoo.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F TISTORY 나를 표현하는 블로그를 만들어보세요. www.tistory.com 문제를 풀 때 항상 완전탐색을 먼저 고려해본다. 부분 문제로 나눌 수 있는게 직관적으로 보여서 그렇게 풀었다. 리턴이 많아서 깔끔해 보이진 않지만 예외 없이 한번에 통과하는 코드를 짜고자 할때 나오는 습관이다. import java.io.*; import java.util.*; public class Main { public static int N; public static int []arr; public static int[][] dp; public static final i..
[백준] 1956 운동 문제링크: www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제를 보자마자 플로이드 워셜로 모든 경로를 저장할 수 있다는 것을 알았다. N이 400이기 때문이다. 정답을 제출한 다음 이것보다 더 빠른 속도를 보이는 풀이를 보니 배열을 초기화 할 때 Arrays.fill을 쓰는 것 같았다. 나도 넣어줬더니 제출결과가 30% 빠르게 나왔다. import java.io.*; import java.util.*; public clas..
[백준] 1504 특정한 최단 경로 문제링크: www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 난 다익스트라를 조금만 응용해도 감을 못잡는 경우가 있는 것 같다. 최단경로 문제를 조금 더 풀어봐야겠다. 최단경로 문제는 재밌기도 하고. 어쨌든 위 문제는 시작점 세 군데에 대해 다익스트라를 수행하면서 정보를 저장했다. 1번 시작점에서 갈 수 있는 모든 최단거리 반드시 들러야 하는 두 곳을 시작점으로 갈 수 있는 최단거리를 저장했다. 이 과정에서 이미 저..

티스토리툴바