본문 바로가기

알고리즘,PS/백준

[BOJ] 백준 [15486] 퇴사 2 JAVA
알고리즘,PS/백준 2023. 10. 6. [BOJ] 백준 [15486] 퇴사 2 JAVA https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 📝문제 📝풀이 하루씩 순차적으로 진행하면서 특정 일의 상담을 진행하고 나서 받는 총 합 이익을 갱신 시켜주면 된다. 특정일을 i 상담 걸리는 시간을 A(i) 페이를 P(i) 페이 총합을 S(i) 라고 했을 때 점화식은 S(i + A(i)) = max( S(i + A(i)), S(i)+P(i) ) 가 된다. 추가로) i 의 범위는 i 번째 상담을 끝 났을 때 i+1 일..
[BOJ] 백준 [1062] 가르침 JAVA
알고리즘,PS/백준 2022. 6. 1. [BOJ] 백준 [1062] 가르침 JAVA https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 📝문제 📝풀이 단순히 문자열 완전탐색으로 풀 수 있었다. 우선, anta tica 부터 5개의 알파벳을 차지하고 시작하므로 k>5 인경우에만 진행해야 한다. pattern matching 함수를 사용하여 만약, 해당 패턴의 단어가 있으면 anta tica를 제외한 부분만 문자열 리스트에 추가한다. 알파벳 방문 체크 배열 visit 을 하나씩 체크하다가 k 개의 갯수가 되었다면 문자열 리스트..
[BOJ] 백준 [2573] 빙산 JAVA
알고리즘,PS/백준 2022. 5. 30. [BOJ] 백준 [2573] 빙산 JAVA https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 📝문제 📝풀이 탐색문제인데 , 탐색할 때 마다 다른 노드에 영향을 끼치는 유형이며 큐를 이용해야 하는 문제이다. isSeprated() 함수로 분리가 되었는지에 대한 검사를 계속 시행하면서 만약 분리가 되지 않은 경우 전 좌표를 살피면서 동서남북으로 바다가 있는지 검사한다. 검사한 결과가 0보다 클 경우 큐에 삽입. if 큐가 비어있을 경우 => 분리 불가능. break import java..
[BOJ] 백준 [13458] 시험감독 JAVA
알고리즘,PS/백준 2022. 5. 30. [BOJ] 백준 [13458] 시험감독 JAVA https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 📝문제 📝풀이 1. 각 시험장 마다 총 감독원이 꼭 있어야 함 2. 시험장 인원을 부감독 수로 나눔 import java.io.*; import java.math.BigInteger; import java.util.*; import java.util.stream.Collectors; import java.util.stream.IntStrea..
[BOJ] 백준 [17136] 색종이붙이기 JAVA
알고리즘,PS/백준 2022. 5. 25. [BOJ] 백준 [17136] 색종이붙이기 JAVA https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 📝문제 📝풀이 이 문제의 핵심은 그리디하게 접근해서는 풀 수 없는 문제이다. 반례) 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0..
[BOJ] 백준 [15787] 기차가 어둠을 헤치고 은하수를 JAVA
알고리즘,PS/백준 2022. 5. 19. [BOJ] 백준 [15787] 기차가 어둠을 헤치고 은하수를 JAVA https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 📝문제 📝풀이 주어진 수의 범위가 커서 비트 마스킹으로 풀어야 하는 문제이다. 0000...00000 으로 총 21개의 0으로 기차의 상태를 체크한다. ( 해당 위치에 1번에 not 을 적용시킨 결과와 and 연산 적용 case 3 => >> 연산으로 한칸 밀어내고 not 연산을 적용시킨 ( 11111110) 과 and 연산 나올 수 있는 모든 경우를 카운트한다. 참고) 비트마스크 연..
[BOJ] 백준 [1052] 물병JAVA
알고리즘,PS/백준 2022. 5. 18. [BOJ] 백준 [1052] 물병JAVA https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 📝문제 풀이 경우의 수 를 하나씩 따져보면 -1 을 출력할 일은 없다. 우선 물통을 안사고 최대한 합친다고 해보자 주어진 n 이 다음과 같을 때 하나씩 보자. case 1 : 0 case 2 : 1 case 3 : 2 1 case 4 : 4 case 5 : 4 1 case 6 : 4 2 ... 남는 물병이 점점 늘어난다. => 병이 모자랄 일은 x 그리고 2^n 의 갯수이면 물병을 사지 않아도 된다. ..
[BOJ] 백준 [17124] 두개의배열 JAVA
알고리즘,PS/백준 2022. 5. 14. [BOJ] 백준 [17124] 두개의배열 JAVA https://www.acmicpc.net/problem/17124 17124번: 두 개의 배열 정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다. A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자. C[i] 는 배열 B에 있 www.acmicpc.net 📝문제 📝풀이 이분탐색 or 이진탐색 문제이다. 해당 위치를 기준으로 앞 뒤를 파악해야 하므로 lower higher 메서드를 제공해주는 TreeSet을 이용한다. B 배열이 기준이므로 B배열을 TreeSet으로 만든다음 A 배열 원소만큼 반복문을 돌린다. 찾은 결과 원소를 result 라고 하면 1. bSet 이 원소 e 를 가지고 있을 경우 => result = ..
LIST
Recent Posts
Popular Posts
Archives
Visits
Today
Yesterday

티스토리툴바