본문 바로가기
728x90

백준브실골124

백준 12783, 곱셈 게임 개요 문제 링크 골드 2, DP 숫자를 자유롭게 이어붙이고, 서로 곱하여 N을 만들 때 곱셈의 최소 횟수 접근 전형적인 재귀 DP문제, 메모이제이션이 필요하다고 생각해서 엄청 헤맸는데 메모이제이션이 필요 없다. 왜냐? 어차피 m이 20개밖에 안돼서 큰 의미가 없다. 풀이는 어떤 수 N을 "이어붙여" 만들 수 있다면 0, 아니라면 약수들에 대해 약수의 dp와 몫의 dp+1을 해주면 된다. 먼저 카드를 받아온 상태에서 set에 모든 이어 붙인 수를 저장해봤다. 메모리 초과가 난다. 그럼 어떤 수가 이어 붙인 수인지 판단하는 함수를 만들었다. 메모리 초과는 해결됐는데 96%에서 시간초과가 난다. 그럼 약수를 하나의 set에 저장해서 사용해보자. 다시 메모리 초과가 나버렸다. 그럼 마지막으로 모든 수의 약수를 .. 2023. 5. 11.
백준 16207, 직사각형 개요 문제 링크 골드 3, Greedy 최대 1차이 나는 두 개의 선분을 양 변으로 하는 직사각형의 넓이의 합의 최댓값 접근 전형적인 그리디 문제, 정렬을 한 뒤 차이가 1 이하이면 순서대로 변으로 사용해주면 되고, 오름차순 정렬 후 가로가 정의되어 있다면 정의된 가로와 곱해서 전체에 더해주고, 정의되어있지 않다면 가로로 정의해주면 된다. 이게 왜 되냐? 하면 우선 길이가 긴 변을 선택해야 하는 건 당연한데, 길이가 가장 긴 두 변을 선택하는 것이 왜 이득인지는 바로 알기 쉽지 않다. 아래의 상황을 가정해보자. a1 > a2 > a3 > a4 여기서 a1×a2+a3×a4가 a1×a4+a2×a3나 a1×a3+a2×a4보다 큰 지 알면 되는 건데, 얼핏 기억나는 건 경시에서 다루는 재배열 부등식이라는 개념을.. 2023. 5. 10.
백준 1570, 오세준 개요 문제 링크 골드 4, 수학, 구현 무한 반복되는 경로에 끝 점이 포함되는 가장 앞선 경로 출력 접근 애드혹 씹드혹 스러운 문제, 헷갈리는 케이스가 많아서 꽤 헤맸다. 처음보면 경로탐색? 응 BFS 하기 쉬운데, 그러면 O(2^50) 의 시간복잡도를 수행할 수 없다. 중간에서 만나기 쓰면 되지 않나? 하면 아무리 생각해도 안된다. 그럼 어떻게 푸는 문제냐? 하면 가능한 케이스를 잘 생각해보면 된다. GCD 같은 걸 쓰지도 않는다. 안되는 경우부터 생각하면 오른쪽 위로만 갈 수 있으니까 왼쪽이나 아래에 있는 경우는 -1을 return 한다. 우선 우리가 관심있는 부분은 dx, dy이므로 두 점의 차이를 계산하고, n개의 R, U 선택지 중 R의 개수를 기준으로 루프를 돌린다. R의 개수를 x, U의 개.. 2023. 5. 7.
백준 27192, Pick a Pair 개요 문제 링크 골드 3, String, Greedy N개의 문자열로 N/2개의 pair를 형성할 때 pair의 prefix의 최소 길이의 최댓값 접근 일단 문제의 핵심은 전체 pair들의 prefix를 생각할 필요가 없다는 것이다. Pair의 prefix의 최소 길이의 최댓값이라는 말라는 말이 엄청 헷갈릴텐데, 먼저 pair를 골라야 하고, 그 조합의 prefix 길이가 최대가 되도록한다고 천천히 생각하면 문제의 구조를 이해할 수 있다. Pair를 고르는 것이 핵심인데, 아래 상황들을 천천히 읽어보자. Pair를 고를 조건, 즉 최소 prefix의 길이가 최대가 되도록 고르는 조건을 생각하는 과정이 상당히 그리디해서 Greedy를 추가했다. 사실 pair의 구성에는 최적의 pair가 항상 존재한다. 그.. 2023. 5. 4.
백준 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

티스토리툴바