PS
BOJ 1344 축구 [Java]
BOJ 1344 축구 1. 문제 링크 https://www.acmicpc.net/problem/1344 2. 문제 해설 중고등학교 때 배웠던 확률 문제이다. 90분까지 5분 간격으로 구간을 나누므로 총 구간의 수는 18개이다. A팀이 구간에서 골을 넣을 확률을 a라고 한다면, 경기 종료까지 A팀이 r골을 넣을 확률 = 18구간 중 골을 넣을 r개의 구간을 선택하는 경우의 수 x 선택된 경우의 수에서 r골을 넣을 확률 = 18Cr x a^r x (1-a)^(18-r) 이다. 18까지의 숫자 중 소수는 2, 3, 5, 7, 11 ,13, 17이므로 위 식에 적용하여 각 팀이 소수로 득점할 확률을 구할 수 있다. A, B팀 중 적어도 한 팀이 골을 소수로 득점할 확률 = A팀이 소수로 득점할 확률 + B팀이 ..
![BOJ 11067 모노톤길 [Java]](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FIWEyV%2FbtrLWlZkNRr%2FePMcJkyNZpikoHUkR0P290%2Fimg.png)
BOJ 11067 모노톤길 [Java]
BOJ 11067 모노톤길 1. 문제 링크 https://www.acmicpc.net/problem/11067 2. 문제 해설 문제에서 설명한 모노톤길의 정의에 의해 x 좌표 방향으로는 무조건 증가한다. 다만, y 좌표의 경우에는 길의 모양에 따라 증가할 수도 있고 감소할 수도 있다. 그렇기 때문에, y축 방향으로 어떻게 정렬을 해주는 지가 이 문제의 핵심이다. 문제 풀이의 흐름을 아래에서 설명하겠다. 1. 일단 입력 받은 좌표들을 x 좌표 오름차순으로 정렬하고, x 좌표가 같다면 y 좌표 오름차순으로 정렬한다. 2. 현재 정렬된 좌표 순서에 따라 모노톤길을 처음부터 따라간다고 생각해보자. 6번 (3, 3) 좌표에서 7번 좌표를 갈 때 (5, 3)으로 가는 것을 기대하지만, 현재 정렬된 순서에 따르면 (..
프로그래머스 Lv.2 예상 대진표 [Java]
1. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12985 2. 문제 해설 간단한 문제였다. a 와 b를 2로 나눠주면서 나눠준 횟수를 구하면 된다.(짝수이냐 홀수이냐는 구분해줘야한다.) 단, 언제까지 나눠줄 것인지 조건을 설정하는 것이 문제의 핵심이다. 조건 1. a 와 b의 차이가 1이어야 함. 조건 2. a 와 b 중 작은 수가 홀수여야함. 예를 들어 a = 4이고 b =5 이면, 차이가 1이지만 한 라운드를 더 치뤄야한다. 위 조건을 동시에 만족할 때까지 a와 b를 나누어주면 된다. 3. 코드 보기 class Solution { public int solution(int n, int a, int b) { int answer =..
프로그래머스 Lv.3 순위 [Java]
1. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49191 2. 문제 해설 순위를 확정 짓는 방법은 생각해내기 쉽다. 자신과 연관된 results 값이 n-1 개면 순위는 확정된다. (이때 n은 총 선수의 수) 문제에서 나온 경우로 예를 들자면, 2번 선수와 관련된 results 값은 [4, 3], [4, 2], [3, 2], [1, 2], [2, 5]이다. 즉, 1, 3, 4번 선수에게는 패했고, 5번 선수에게는 이긴 것이다. 자신과 관련된 경기 결과가 4개이므로 순위가 확정되었다. 2번 선수의 경우는 처리하기 쉽지만, 여기서 문제는 5번 선수와 같은 경우를 어떻게 처리할 것인가이다. 5번 선수는 주어진 results 값에서 자신과..
BOJ 1939 중량제한 [Java]
BOJ 1939 중량제한 1. 문제 링크 https://www.acmicpc.net/problem/1939 2. 문제 해설 처음에는 실수로 시간복잡도를 생각 안하고 접근했다. 공장이 있는 섬 두 개 중 한 지점에서 다른 지점까지 갈 수 있는 모든 경로를 살펴보면서 각 경로마다의 최소의 중량제한을 구하고, 그 값의 최대값을 구하는 방식을 dfs로 구현하였다. 시간복잡도가 O(NM)으로 당연히 시간초과가 나왔다. 시간복잡도를 줄일 수 있는 방법이 무엇이 있을까 고민하다가, 각 다리의 중량제한의 범위가 1 ≤ C ≤ 1,000,000,000 으로 굉장히 큰 것을 보고 이분탐색을 떠올렸다. BFS와 이분탐색을 이용해서 풀 수 있는데, 각 로직의 흐름을 설명해보겠다. 이분탐색 로직 이분탐색을 할 대상은 물품의 중..