본문 바로가기

알고리즘/백준 문제풀이39

백준 [자바 java] 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 오랜만에 백준이다! 코드트리를 통해서 개념을 어느정도 익혔으니 실전에 적용해보는 연습을 슬슬 해보려고 한다. 이 문제는 내가 5개월 전에 시도했다가 못풀었던 문제이다. 집의 위치와 공유기의 수가 주어지고, 이를 적절하게 배치해서 공유기가 설치된 집 사이의 가장 가까운 거리가 최대가 되도록 해야한다. 이 문제는 이진탐색으로 풀었고, lowerBou.. 2023. 9. 14.
백준 [자바 java] 10797 : 10부제 https://www.acmicpc.net/problem/10797 10797번: 10부제 서울시는 6월 1일부터 교통 혼잡을 막기 위해서 자동차 10부제를 시행한다. 자동차 10부제는 자동차 번호의 일의 자리 숫자와 날짜의 일의 자리 숫자가 일치하면 해당 자동차의 운행을 금지하는 www.acmicpc.net 첫번째 줄에 한자리 수가 주어지고 두번째 줄에 주어진 5개의 수 중 일의자리가 이와 일치하는 수의 갯수를 출력하는 문제이다. 일의자리 수는 해당 수를 10으로 나눈 나머지와 같으므로 이와 비교하는 방식으로 문제를 풀었다. import java.io.*; import java.util.*; import java.math.*; public class Main { public static void mai.. 2023. 8. 9.
백준 [자바 java] 12904 : A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 처음에는 dfs로 풀었는데 시간초과가 났다. 그래서 더 효율적인 방법을 찾다가 완성된 문자열에서 처음 문자열로 돌아가는 방법을 쓰게 되었다. 문자열의 제일 끝이 A이면 이전에 기존 문자열 끝에 A를 썼다는 의미이므로 A를 뺴고 그대로 두면 되고, B이면 B를 빼고 문자를 뒤집으면 된다. 이를 반복하다가 문자가 아예 사라지면 break를 통해 나오고 안된다는 결.. 2023. 8. 4.
백준 [자바 java] 5338 : 마이크로소프트 로고 https://www.acmicpc.net/problem/5338 5338번: 마이크로소프트 로고 마이크로소프트 로고를 예제 출력처럼 출력하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 단순히 프린트 하는 문제입니다! 문제에 있는 입력을 복사해서 System.out.println()에 넣어주세요 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ System.out.println(" _.-;;-._\n" + "'-..-'| || |\n" + "'-..-'|_.-;;-._|\n" + "'-..-'| || |\n" + "'-..-'|.. 2023. 8. 2.
백준 [자바 java] 10807번 : 개수 세기 https://www.acmicpc.net/problem/10807 10807번: 개수 세기 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거 www.acmicpc.net 오랜만에 쉬운 문제를 가져왔다! -100부터 100까지의 수를 입력받고, 특정 수가 주어지면 해당 수가 몇 번 나왔는지 출력하는 문제이다. 나는 배열을 만들어서 수를 입력받을 때마다 해당 인덱스의 수를 하나씩 늘려주는 방식을 사용했다. 이때 인덱스가 음수가 될 수는 없으니까 200크기의 배열을 만들고, 입력받은 수에 100을 더한 인덱스의 값을 늘려주었다. 그럼 -100이 입력되었을 .. 2023. 8. 1.
백준 [java 자바] 9084 : 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 이 문제를 보자마자 언젠가 풀었던 문제인 것 같은데? 라는 생각이 들긴 했다. dp를 사용하고, 점화식을 구해서 풀어야 한다는 것 까지는 알아냈지만 여기서 어떻게 해야 할지 도저히 감이 잡히지 않아서 사람들의 풀이법을 검색해서 배웠다. 일단 풀이법을 그림으로 정리해보았다. 글씨가 정말 별로지만, 이해하는데는 확실히 도움이 되었다. 일단, 동전의 수가 주어지고 동전의 액수가 들어오면.. 2023. 7. 25.

티스토리툴바