본문 바로가기

PS/BOJ14

[BOJ] 20056 마법사 상어와 파이어볼 문제 링크 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치� www.acmicpc.net 2020년 하반기 새로운 상어 시리즈가 등장했습니다...! 마법까지 쓰게 될 줄이야... 모든 시뮬레이션 문제가 그렇지만 정말 위의 내용을 착실하게 구현하면 됩니다. 다른 상어 시리즈에 비해서 구현 난이도가 어렵지 않았습니다. 현재 위치(x,y), 질량(m), 방향(d), 속력(s)을 속성으로 갖는 파이어볼 구조체를 정의합니다. 파이어볼은 두 개.. 2020. 10. 19.
[BOJ 3025] 돌 던지기 문제 링크 https://www.acmicpc.net/problem/3025 3025번: 돌 던지기 이 모든 사건의 시작은 2주 전이었다. 그 날 상근이는 복도에 누워서 잠을 자고 있었다. 커다란 돌을 들고 그 옆을 지나가던 민혁이는 복도에서 잠을 자는 사람을 처음봐서 신기하게 쳐다보고 있 www.acmicpc.net 시뮬레이션 문제는 많이 다뤄서 자신있었는데 시간초과를 해결하는데 오래 걸린 문제다 순진하게 구현했다가는 O(RN)으로 TLE를 맞기 십상이다 (_ㅠㅠ_) O(RN)에서 쿼리수에 해당하는 N을 줄일 순 없다 N개의 각 쿼리당 곱해지는 O(R)을 줄이는 방법을 생각해보자 아이디어 기본 하나의 열 안에서 돌이 'O'나 'X'를 만나기 전까지 떨어지는 것을 시뮬레이션의 한 단위라고 생각해보자 돌이.. 2020. 9. 2.
[BOJ 16890] 창업 문제 링크 https://www.acmicpc.net/problem/16890 16890번: 창업 입력은 길이가 N(1 ≤ N ≤ 300,000)인 문자열 두 개로 이루어져 있다. 모든 문자열은 알파벳 소문자로만 이루어져 있다. 첫 번째 줄에 주어지는 문자열은 구사과가 고른 문자이고, 두 번째 줄에 주�� www.acmicpc.net 아이디어 게임의 진행은 구사과부터 순서대로 한 턴씩 진행되기 때문에 게임이 N턴 뒤에 끝난다고 할 때, 구사과는 (N + 1) / 2 번의 턴을, 큐브러버는 N / 2번의 턴을 갖는다 구사과는 사전순으로 가장 앞서는 문자열을 만들고 싶어 하므로 갖고 있는 n개의 알파벳 중에서 작은 순서대로 (n+1) / 2 개의 알파벳만을 사용해야 한다 마찬가지로 큐브러버는 사전순으로 가장.. 2020. 8. 31.
[BOJ 1310] 달리기 코스 문제 링크 https://www.acmicpc.net/problem/1310 1310번: 달리기 코스 첫째 줄에 기둥의 개수 N(1≤N≤100,000)이 주어지고, 이어서 N줄에 걸쳐 각 기둥의 좌표를 나타내는 정수 두 개가 주어진다. 좌표의 절댓값의 범위는 50,000을 넘을 수 없다. www.acmicpc.net 아이디어 - 좌표 평면위의 여러 점들 중 가장 먼 거리의 두 점은 convex hull 위에 존재한다 => convex hull (Graham's scan) 알고리즘 - convex hull에서 두 쌍의 연속한 두 점을 잡아 벡터를 만들고 v1 = p[i+1] - p[i] ... (p[i], p[i+1]) v2 = p[j+1] - p[j] ... (p[j], p[j+1]) 두 벡터의 ccw가.. 2020. 8. 26.
[BOJ 16480] 외심과 내심은 사랑입니다 문제 링크 https://www.acmicpc.net/problem/16480 16480번: 외심과 내심은 사랑입니다 수진이는 외심과 내심 없이는 살 수 없다고 말할 정도로 외심과 내심을 사랑한다. 하지만, 갑자기 수진에게 어려운 일이 닥쳤다. 바로 평면에 있는 삼각형 ABC에서 외접원의 반지름의 길이 R이고, www.acmicpc.net 아이디어 오일러 삼각형 정리를 아는지 묻는 기하문제이다. 위 정리는 삼각형의 외심과 내심 사이의 거리를 외접원과 내접원의 반지름을 통해 나타내는 정리이다. d : 외심과 내심 사이의 거리 R : 외접원의 반지름 r : 내접원의 반지름 오일러 삼각형 정리는 각 변수를 위와 같이 정의할 때 다음과 같다. 오일러 삼각형 정리 증명 오일러 삼각형 정리의 증명에 쓰이는 "방멱정.. 2020. 7. 28.
[BOJ 18870] 좌표 압축 문제 링크 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 아이디어 '좌표압축' 기법은 PS에서 종종 쓰이는 기법으로, 큰 범위의 값을 갖는 좌표들을 정렬하여 다시 순서를 부여함으로써, 더 작은 범위 내로 압축 시키는 것이다. 가령 1차원 x축 위의 [1, 1e9] 의 값을 갖는 어떤 1만 개의 좌표를 생각해보자. count[t] = x축의 값이 t인 좌표의 개수라고 할 때, t = [1, 1e.. 2020. 7. 16.

티스토리툴바