알고리즘/백준33 [백준 1072 / 게임 / JAVA / 이분 탐색] https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 문제 접근 다른 건 어렵지 않게 해결했으나 승률을 지정하는 방법에서 막혔다. 처음에 승률을 지정할 때 (double)Y / (double)X * 100로 지정해주었으나 이렇게 했을 경우 Y에 비해 X가 너무 크면 100을 곱하기도 전에 값이 0.000000..... 에 가까워져서 안된다고 하더라 그래서 (double)Y * 100 / (double)X 이렇게 100을 앞으로 당겨와서 곱해야.. 2023. 5. 10. [백준 15810 / 풍선 공장 / JAVA / 이분 탐색] https://www.acmicpc.net/problem/15810 15810번: 풍선 공장 1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 www.acmicpc.net 문제 접근 다른 건 다 제대로 적어놓고 범위를 지정하는데서 애 먹었다. left는 0이나 1로 해도 통과 right의 값을 현재 풍선 만드는데 가장 오래 걸리는 사람의 시간 * 풍선 갯수로 잡아줘야한다. 내가 적은 코드 상엔 시간이 정렬된 배열의 마지막 인덱스를 가져와서 최소 풍선 갯수랑 곱한 값으로 right값을 지정해놨는데 이론상 최대 시간은 1000000.. 2023. 5. 9. [백준 / 그르다 김가놈 / JAVA / 이분 탐색] https://www.acmicpc.net/problem/18113 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 문제 접근 주어진 김밥 길이를 꼬다리를 정리 후 배열에 저장, 꼬다리 길이에 못미치는 김밥은 폐기 저장된 배열 김밥 길이들을 토대로 김밥 최소 갯수를 만들 수 있어야 하며 자르는 김밥의 길이도 최대로 해주고 싶다. 자르고자 하는 김밥의 길이가 길수록 만들 수 있는 김밥의 갯수는 줄어들 것이다. mid 전체 길이를 반씩 자르면서 최적의 김밥 길이를 찾아야한.. 2023. 5. 7. [백준 / 예산 / JAVA / 이진 탐색] https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 접근 예산액을 배열로 만들고 값을 저장, 이 문제에선 배열을 정렬안하고도 풀 수 있던데 난 일단 정렬해서 풀었다. 총 요청 예산액이 총 예산보단 작다면 가장 큰 요청 예산액을 출력 아니라면 상한액을 탐색해 나간다. 상한액은 반씩 잘라가면서 탐색해가고 배열 값들과 현재 상한액을 비교하면서 작은 값은 그대로 합하고 큰 값은 상한액을 더한다. 더한 총 값이 총 예산보다 작으면 return시켜.. 2023. 5. 6. [백준 / 입국심사 / JAVA / 이진탐색] https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 문제 접근 int 타입의 범위를 벗어난 값들은 long타입으로 지정해주자 문제의 핵심은 반씩 시간을 줄여가면서 mid에 해당하는 시간이 통과해야되는 인원을 모두 포함하면서 최소여야한다. while문에서 통과해야되는 인원을 충족했을 때의 시간을 계속 저장해가는데, 왼쪽 범위가 오른쪽 범위를 넘기 직전까지 계속 돌기 때문에 범위가 가장 좁혀졌을 때 인원을 충족한 시간 값이 result에.. 2023. 5. 4. [백준 9934번 / 완전 이진 트리 / JAVA / DFS] https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 문제 접근 익숙하지 않은 형태라 정답에 도달하기 힘들어 방법을 참고하였다. 핵심은 노드 방문 순서가 담긴 배열을 반씩 쪼개가며 중간값을 해당 깊이 list에 삽입한다. dfs라 왼쪽 노드부터 쭉 탐색해간다. 마지막 왼쪽 노드에 도달할 경우 시작 인덱스와 마지막 인덱스의 번호가 [0, 0]이라 중간 인덱스는 0이 되어 arr[0] 값이 해당 깊이 list에 담기게 될 것이다.. 2023. 5. 1. 이전 1 2 3 4 5 6 다음
