본문 바로가기
728x90

백준브실골/기타22

백준 13258, 복권 + 은행 개요 문제 링크 골드 5, 수학 가진돈 만큼의 확률로 J원을 줄 때 C기간 뒤 금액의 기댓값 접근 고등학생 때 확통을 열심히 배워야 하는 이유. 기댓값이란 어떤 확률적 시행에 대해 모든 경우의 수를 따져봤을 때 내가 얻을 수 있는 값이다. 쉽게 생각해 A (1% 확률로 100억) vs B (50% 확률로 1억) 중 더 이득인 것을 고를 때 기댓값을 사용한다. 1%의 확률로 100억이 더 손해일 것 같지만 A의 기댓값은 1억, B의 기댓값은 5000만원이라 A가 이득이다. 비슷하게 이 문제를 바라보자. 다음의 과정을 거치기만 하면 문제를 풀 수 있는데, 1회 시행 후 누군가는 J원을 얻는다. 어떤 $a_i$원을 가진 i번째 사람이 얻을 값은 $p_i$ × J = ($a_i$ / $a_i$의 총합) × J원.. 2024. 2. 7.
백준 22887, Reversort Engineering 개요 문제 링크 골드 5, 정렬, 구성적 i의 위치를 찾아 뒤집으며 정렬할 때 뒤집는 부분수열의 길이의 합이 C가 되는 수열 구하기 접근 재밌는 구성적 문제, 코포의 단골문제이다. 핵심은 만약 i를 찾아 뒤집었다면, a[i]=i를 항상 만족하고, j (n * (n + 1)) / 2 - 1) return false; vec ans(n); for (int i = 0; i = 1; i--) { rev(ans, i - 1.. 2023. 7. 16.
백준 15670, 도로 공사 개요 문제 링크 골드 2, 누적합 구간 L,R을 뒤집었을 때 증가하는 연속부분수열 개수 구하기 접근 먼저 N을 보자. 10만이니까 O(NlogN)이상은 사용할 수 없다. 아하 O(N)안에 끝내라는 말이구나. O(N)안에 끝내는 가장 좋은 방법은 연산에 필요한 데이터를 만들어두고, O(1)안에 연산을 마치는 것이다. 보통 이런 유형의 문제에 누적합을 사용한다. 누적합을 어떻게 사용하냐? 하면 우선 문제를 풀 방법부터 생각해보자. 배열을 직접 뒤집어서 매번 오르막을 세어주는 것이 가장 쉽게 생각할 수 있는 방법이고 가장 오래걸린다. 뒤집는데 O(N), 세어주는데 O(N)이 걸리니까 O(MN)으로 1e10번 연산이 필요하다. 시간초과. 그럼 (L,R)에 대한 오르막과 내리막을 전부 저장한 뒤, (1,L-1)의.. 2023. 5. 12.
백준 1570, 오세준 개요 문제 링크 골드 4, 수학, 구현 무한 반복되는 경로에 끝 점이 포함되는 가장 앞선 경로 출력 접근 애드혹 씹드혹 스러운 문제, 헷갈리는 케이스가 많아서 꽤 헤맸다. 처음보면 경로탐색? 응 BFS 하기 쉬운데, 그러면 O(2^50) 의 시간복잡도를 수행할 수 없다. 중간에서 만나기 쓰면 되지 않나? 하면 아무리 생각해도 안된다. 그럼 어떻게 푸는 문제냐? 하면 가능한 케이스를 잘 생각해보면 된다. GCD 같은 걸 쓰지도 않는다. 안되는 경우부터 생각하면 오른쪽 위로만 갈 수 있으니까 왼쪽이나 아래에 있는 경우는 -1을 return 한다. 우선 우리가 관심있는 부분은 dx, dy이므로 두 점의 차이를 계산하고, n개의 R, U 선택지 중 R의 개수를 기준으로 루프를 돌린다. R의 개수를 x, U의 개.. 2023. 5. 7.
백준 25331, Drop 7 개요 문제 링크 골드 5, 구현, 시뮬레이션 같은 행/열에 있는 원소 개수만큼의 값이 적힌 원소를 동시에 지울 때 가장 최적의 낙하 위치 찾기 접근 실수하면 상당히 골머리 썩을 문제, 낙하 + 덩어리 개수세기 + 배열 변형까지 3요소가 있는 문제는 골 3에서도 많이 봐서 골3 정도로 가도 될 것 같은데 예시 설명이 너무 자세해서 골4에 투표했다. 문제가 쉬워지는 건 배열 크기가 49밖에 안돼서 걍 최적화 할 방법이 생각나지 않으면 4중 루프를 돌려버리면 되기 때문이다. 하나씩 생각해보자. 우선 개수세기, 이게 한 줄당 원소 개수가 아니라 덩어리진, 즉 연속진 원소의 개수임을 잘 생각해야 한다. 그럼 덩어리 내 원소가 존재하는 왼쪽이나 위로 최대한 이동한 뒤 아래나 오른쪽 끝으로 이동하면 된다. 다음 낙하.. 2023. 5. 4.
백준 4422, Crypt Kicker II 개요 문제 링크 골드 4, String, Hash Permutation을 이용해 문자열 decoding 접근 문제 해석이 조금 까다로울 수 있는데, 각각의 알파벳을 일대일 대응으로 변환한 암호문이 주어지면 원문을 복원하는 문제이다. 이때 복원 규칙을 알 수 있도록 특정 문장을 사용했는데, 그 문장이 바로 the quick brown fox jumps over the lazy dog 이다. 따라서 저 문장의 암호화로 나올 수 있는 문장을 찾은 뒤, 규칙을 설정하고 복호화해서 출력하면 된다. 그럼 변환 가능성은 어떻게 판단하냐? 하면 여러 방법이 있겠지만 나는 모든 알파벳의 위치를 저장한 뒤, 위치 집합이 같은지 봤다. 어떤 알파벳인지 몰라도 된다. 예를들어 {(1,3), (2,5,6), (4)}와 같이 위.. 2023. 5. 4.
백준 27715, 우표 구매하기 (Easy) 개요 문제 링크 골드 4, 조합론 1, 2원짜리 우표를 중복을 허용하여 선택해 K원 구성하기 접근 대표적인 중복조합 문제, K를 1, 2의 단위로 쪼개보자. 2원짜리를 i개 쓴다고 하면 K = (i×2) + (K-i×2)가 되는데, 2원짜리를 i개 고르는 방법은 M개의 2원짜리 동전 {q1, q2, ... qM}에서 아래의 식을 구성하는 방법의 수이다. q1+q2+...+qM = i 나머지 1원짜리를 K-i×2개만큼 고르는 방법도 마찬가지로 적용할 수 있다. N개의 1원짜리 동전 {p1,p2, ... pN}의 개수의 합이 K-2×i가 되면서 각 동전별 구분이 없고 중복을 허용하므로 아래와 같이 표현할 수 있다. p1+p2+...+pN = K-2*i 나머지는 수능 확통을 복습해보자. 위와 같은 식이 주어지.. 2023. 5. 4.
백준 4843, Coin Toss 개요 문제 링크 골드 3, 확률론 지도에 동전을 던져 1개부터 4개의 칸을 덮을 확률 구하기 접근 생각이 조금 까다로울 수 있는데 예시가 3개나 나와서 예시만 맞으면 크게 틀릴 일 없는 문제. 기하학 태그가 걸려있는데 큰 연관성은 없다. 잡다한 말은 접어두고 아래 그림 하나로 정리할 수 있다. 아래 그림을 따라 체크해보면서, 마지막에 S1+S2+S3+S4가 N×M×T×T와 같은지 확인해 재차 점검해준다. 마지막으로 전체 넓이로 나눈 뒤 100을 곱해 출력해주면 된다. 의사코드는 의미 없을 것 같아 생략했다. Source code #include using namespace std; using ld=double; ld PI=acos(-1); void test() { ld m,n,c,t; cin>>m>>n>.. 2023. 5. 4.
백준 3284, MASS 개요 문제 링크 골드 5, Stack 탄화수소의 분자량 구하기 접근 화1 선택자라면 지긋지긋할 탄화수소이다. 내 기억에 C4H8이 8개였나 그랬는데 -CH3, -CH2, -CH1, C 개수를 다 외워버렸던 기억이 난다. 문제로 돌아와서, 일반적인 괄호 문제랑 매우 유사하다. 4928과 풀이가 거의 비슷하니 이해를 위해 같이 읽어보길 바란다. 만약 괄호가 열린다면 depth를 하나 추가한다. depth는 왜 설정하냐 하면 괄호가 닫힐 때 depth-1 번째에 값을 더해줘야 하기 때문이다. 말이 어려운데, 이런 식을 생각하자. ((1+2x3)x3+1) = ((D2)x3+1) = D1 괄호 안에 덩어리를 괄호의 개수에 맞게 기호로 바꿔 D1, D2로 표현할 수 있다. 다음은 재귀적으로 접근하는 것이다. D2를.. 2023. 5. 4.
백준 14921, 용액 합성하기 개요 문제 링크 골드 5, Bisect, 두 포인터 두 수의 합의 절댓값을 최소로 만드는 합 구하기 접근 보자마자 이분탐색을 생각했는데 두 포인터가 정해였다. 이분탐색은 쉽게 생각할 수 있지만 잔 실수가 나기 쉽고, 두 포인터는 실수가 없지만 생각이 어렵다. 이분탐색은 배열 내 x에 대해 -x를 찾아주면 된다. Lower bound를 써주면 되고, 안전하게 가려면 양 옆의 것도 같이 확인해주면 된다. 두 포인터는 왼쪽 오른쪽의 두 수를 더해줄 것인데, 만약 어떤 두 수의 합이 음수에서 양수로 변한다면 절댓값은 앞으로 계속 커진다. 그래서 바뀌는 구간에서 오른쪽을 한 칸 당겨준다. 나머지는 왼쪽칸을 하나 당기면서 탐색하면 된다. Pseudo code update(min, x) { if (abs(x)n; v.. 2023. 5. 3.
728x90

티스토리툴바