본문 바로가기
728x90

코딩테스트/BOJ

 (49)
[백준] 1451. 직사각형으로 나누기 - JAVA https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 50보다 작거나 같은 자연수이 www.acmicpc.net 와 이 문제 푸는데 거의 2시간 걸린듯,,, 왜이렇게 어렵지,,, 어렵다기보다 사각형 넓이 구하는 과정이 헷갈림 인덱스들 맞추는거,,,ㅠㅠ 암튼 참고한 블로그 내용을 설명해보겠다 직사각형을 나누는 방법 3개의 직사각형으로 나눌 수 있는 경우의 수는 위의 6가지가 전부이다 그래서 그냥 다 구해보는 수 밖에 없다~ 직사각형의 합을 구하는 방법 이걸로는 미리 sum 배열을 만들어둔다 해당 ..
[JAVA] 백준 11724번 - 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 각 노드가 몇 개나 연결되었는지 구하면 되는 문제다 그래서 난 DFS를 활용해서 풀었다 약간 고민했던 점은 dfs를 호출할 떄마다 answer++ 를 하면 각각 나눠진 영역의 개수를 구하게 된다 그래서 연결된 요소들의 개수를 구하기 위해 dfs가 호출되고 visited의 수가 바뀔때마다 answer를 증가해야할 줄 알았는데?! 아니었네..
[JAVA] 백준 2179번 - 비슷한 단어 https://www.acmicpc.net/problem/2179 2179번: 비슷한 단어 첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다. www.acmicpc.net 문제 설명이 투박했던 문제.. 풀이 과정도 고민 시간도 그리 길지 않았는데 도대체 문자열 선택 기준이 어케 되는지 헷갈렸당 그냥 모든 문자열끼리 다 비교하고 비슷한 알파벳 수가 많은 단어를 앞에서부터 2개 출력하면 되는거였음~ 자바 코드) import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class boj2179 { public stati..
[JAVA] 백준 9095번 - 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이거 백준 강의 들을 때 풀었던 문젠데 고새 까먹음,, 나 완전탐색 진짜 못하는 듯,,, 역시 코테는 꾸준히 해야하나부다... 암튼... 이거 풀이 참고해서 풀었고 아래는 코드! 자바 코드) import java.util.Scanner; public class Main { static int dp[] = new int[11]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scan..
[그리디] 백준 11399번 ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이) 그냥 배열 정렬하고 앞에서부터 더한 값으로 배열 바꿔주고 전체 더한 값 return함 아마 코드보면 그냥 이해갈 정도로 쉬움! 자바 코드) import java.util.Arrays; import java.util.Scanner; public class boj1931 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n ..
[JAVA] 백준 2512번 - 예산 이 문제는 이분탐색을 통해 해결이 가능했다 이분 탐색의 기준은 인덱스가 아닌 예산이 된다 예산을 기준으로 시행하며 만약 m이 예산의 합보다 작으면 임계치(mid)를 1 감소하고, m이 더 크면 예산 배정이 더 가능한지 확인해야 하니까 1을 더해서 확인해본다 처음엔 좀 어려웠는데 2번 푸니까 이해가 간다! 아래는 코드! 자바 코드) import java.util.Arrays; import java.util.Scanner; public class boj2512 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int answer=0; int n = sc.nextInt(); int[] budgets = new int[..
[JAVA] 백준 14916번 - 거스름돈 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 풀이) 근로 점심시간에 낮잠자고 비몽사몽 백준을 보다가 내가 못푼 문제가 있는거 아니겠어?! 내가?? 하면서 봤더니 거스름돈이네ㅋㅋㅋㅋㅋㅋㅋ 그래서 눈 반만 뜨고 풀었는데 이게 풀리네 나 자신,, 나름 성장하고 있는걸지도,,? 오이오이~~~ 암튼 풀이는 간단했음 이런 DP문제는 최소 동전이니까 큰 금액 동전으로 줄 수 있는만큼 주고 남은 돈은 작은 동전으로 거슬러 주면 된다 근데 딱 안나눠질수도 있으니까 난 반복문으로 풀었다 이 문제는 2원이랑 5원 뿐이니까 5원으로 거스름돈을 나눌 수 있는 최댓값을 기준으로 반복문..
[JAVA] 백준 2606번 - 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이) 처음에 이 문제 보고 아 어렵네,,, 했는데 저기 문제에 뭐라고 써있는지 알아? 초등부..? 2004년도 초딩들,,, 대단했네,,, 이거 보고 갑자기 잠이 깨고 머리가 돌더니 문제를 풀어버림 내가 본선 중등부까지는 비벼봐야되지 않겄어?! 이건 인접리스트로 풀었다 배열로 주어지는게 아니니까 이중 ArrayList로 선언하고 풀었다 저번에 풀었던 백준 1260번(DFS와 BFS) 였나? 그 문제랑 ..
728x90

티스토리툴바