본문 바로가기

PS/BOJ57

백준 14860 / C++ https://www.acmicpc.net/problem/14860 14860번: GCD 곱 N과 M 이 주어졌을 때, GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구하는 프로그램을 작성하시오. www.acmicpc.net [ 풀이 ] 어려운 문제였다. 각 소인수마다 최대지수를 구해주면 되는데 구하는 과정이 어렵다. 2의 최대지수를 구해보자. 2의 최대지수를 구할 때 n/2 * m/2 가 짝수인 쌍의 개수이다. 이때, 4의 최대지수를 구할 땐 2의 최대지수를 구하는 과정에서 값이 1번 세졌다는 사실을 이용한다. 4=2.. 2022. 8. 12.
백준 3830 / C++ https://www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net [ 풀이 ] 오프라인 쿼리로 계산해주면 쉽다. unkown은 미리 처리해주는것에 유의하자. 거리를 그래프에 담은 후 dfs로 순회하면서 연결된 것끼리 거리를 전처리해주고 차이를 구하면 된다. [ Code ] #include using namespace std; using ll = long long; const int MAX = 100010; ll n, m, a, b, .. 2022. 8. 12.
백준 2873 / C++ https://www.acmicpc.net/problem/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net [ 풀이 ] 홀수인 변이 있다면 전부 방문할 수 있음은 자명하다. 모두 짝수인 경우의 문제를 풀자. 규칙을 찾아보자. 전부 방문하는건 불가능하다. 증명은 다음과 같다. 전부 방문하려면 (r-1)(c-1)개의 화살표가 필요하다. 이 값은 홀수이다. 그런데 시작점에서 끝점으로 가는데엔 짝수번의 화살표가 필요하다. 따라서 홀짝성에 위배된다. 그럼 되도록 1개만 제외하고 방문하고 싶다. 이런 문제의 .. 2022. 8. 12.
백준 21761 / C++ https://www.acmicpc.net/problem/21761 21761번: 초직사각형 1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자. 선분의 크기는 변수 $A$로, 직사각형의 크기는 두 개의 변수 $A$와 $B$로, 직육면체의 크기는 세 개 www.acmicpc.net [ 풀이 ] 부피 ABCD에서 한 변을 증가시키면 (A+U)BCD가 된다. 그럼 매번 변화시키면서 1+U/A가 커지도록 해주면 된다. 그리디하게 매번 A,B,C,D중 제일 큰 U를 뽑아서 1+U/x가 제일 큰걸 매번 뽑아주면 된다. 기존 ABCD에서 이렇게 가장 큰 비율을 매번 곱해줘야 최대가 되는건 자명하다. 그 비율이 1보다 크기 때문에 항상 값이 커지기 때문이다. 매번 제일 큰 .. 2022. 8. 8.

티스토리툴바