PS/BOJ
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)으로 가는 것을 기대하지만, 현재 정렬된 순서에 따르면 (..
BOJ 1939 중량제한 [Java]
BOJ 1939 중량제한 1. 문제 링크 https://www.acmicpc.net/problem/1939 2. 문제 해설 처음에는 실수로 시간복잡도를 생각 안하고 접근했다. 공장이 있는 섬 두 개 중 한 지점에서 다른 지점까지 갈 수 있는 모든 경로를 살펴보면서 각 경로마다의 최소의 중량제한을 구하고, 그 값의 최대값을 구하는 방식을 dfs로 구현하였다. 시간복잡도가 O(NM)으로 당연히 시간초과가 나왔다. 시간복잡도를 줄일 수 있는 방법이 무엇이 있을까 고민하다가, 각 다리의 중량제한의 범위가 1 ≤ C ≤ 1,000,000,000 으로 굉장히 큰 것을 보고 이분탐색을 떠올렸다. BFS와 이분탐색을 이용해서 풀 수 있는데, 각 로직의 흐름을 설명해보겠다. 이분탐색 로직 이분탐색을 할 대상은 물품의 중..
BOJ 15685 드래곤 커브 [Java]
BOJ 15685 드래곤 커브 1. 문제 보기 https://www.acmicpc.net/problem/15685 2. 문제 해설 구현 문제다. 구현 문제는 내가 구현해야할 기능이 무엇인가를 파악하면 풀이의 방향이 보인다. 이 문제는 2가지 기능을 구현해주면 된다. 첫번째는 드래곤 커브를 그리는 기능, 두번째는 그린 후 크기가 1×1 인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 파악하는 기능이다. 두 기능을 구현해보자. 1. 드래곤 커브를 그리는 메서드 - drawDragonCurve 메서드 이 메서드를 구현하는 것이 상당히 어려웠다. 정확히 말하자면 구현이 어려웠다기보다는 드래곤 커브가 세대가 늘어날 때 추가되는 선의 규칙을 찾는 과정이 쉽지가 않았다. 세대가 늘어날때 드래곤 커브..
BOJ 14499 주사위 굴리기 [Java]
BOJ 14499 주사위 굴리기 1. 문제 링크 https://www.acmicpc.net/problem/14499 2. 문제 해설 구현 문제에서는 크게 어떤 기능을 구현해야할지를 우선적으로 생각하는 편이다. 하나의 명령의 흐름은 명령을 받으면 주사위를 굴리고 주어진 조건에 따라 값을 업데이트 해주는 것이다. 그러므로 구현해야할 기능은 크게 2가지이다. 첫번째는 주사위를 굴리는 메서드, 두번째는 주사위를 굴린 후 값을 업데이트 하는 메서드이다. 1. 주사위를 굴리는 메서드 - roll 메서드 주사위를 굴리는 건 노가다 방식으로 해결했다. 주사위 정보를 담고 있는 배열과 똑같은 배열을 하나 만들어준다. 그 후 이동하는 방향에 따라 바뀌는 주사위 정보를 바꿔준다. 2. 주사위를 굴린 후 값을 업데이트 하는 ..