김머성 블로그

[BAE/<JOON> 문제풀이] 1132. 합

https://www.acmicpc.net/problem/1132 1132번: 합 N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 www.acmicpc.net 핵심:: 그리디긴 한데 구현에 더 가까운 문제같다. 풀이:: 우선 알파벳들이 각각의 자리에서 몇번씩 나오는지 계산하고 그 값을 숫자로 치환한다. 10의 자리에서 한번 출현, 1의 자리에서 12번 출현 -> 22 로 치환 해당 값들을 크기 순으로 내림차순 정렬하고 높은 값부터 큰 숫자를 주고 값을 계산하면 된다. 의견:: 그리디같은 구석이 없어서 풀 만한 문제 코드:: 더보기 #include #inclu..

[BAE/<JOON> 문제풀이] 14925. 목장 건설하기

https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하 www.acmicpc.net 풀이:: 목장 모양이 정확하게 정사각형이어야 하므로 DP[x][y] = 그 칸을 포함하며 좌상단으로 확장하는 정사각형 크기 중 MAX 으로 정의하면 dp[x - k][y - k] 값 들을 검사하다 이미 탐색된 값을 발견하면 해당 지점부터는 정사각형이 있는 것이 확정되므로 중복 계산하지 않을 수 있다. 맵으로 표현하면 다음과 같다. 1110 1110 1110 0000 이렇게 생긴 맵에서 좌상단부터 ..

[BAE/<JOON> 문제풀이] 1322. X 와 K

https://www.acmicpc.net/problem/1322 1322번: X와 K 첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 핵심:: 비트 연산 구현 문제 풀이:: X | Y = X + Y 는 X와 Y를 2진수로 변환 했을 때 각 자리가 모두 다르다는 것을 의미한다. 따라서 주어진 X에 대해서 2진수 Y가 1을 사용할 수 있는 자리는 정해져 있다. X와 K의 최댓값은 2,000,000,000 이므로 계산해보면 2진수의 최대 자리수는 31자리 이다. X의 최댓값 2진수는 31자리이므로 그보다 큰 2 * 10^9 번째 수는 2^31 + (2 * 10^9) * 2^32 이다. 하지만 모든 자리가 1이어야 31자리 이상의 자..

[BAE/<JOON> 문제풀이] 13334. 철로

https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 핵심:: 문제 카테고리가 라인 스윕이고 정확한 풀이 로직이 정해져 있지 않아서 핵심을 정확하게 뭐라고 쓰기 애매하다. 강의실 문제와 비슷하여 해당 문제 풀이에서 영감을 받았다. 풀이:: 라인 스위핑은 기본적으로 주어진 배열 정렬하고 순회하며 답을 찾는 알고리즘을 의미한다. 시작 위치는 편의상 출근길의 시작 지점으로 고정한다. 주어진 L보다 출근길..

[BAE/<JOON> 문제풀이] 14621. 나만 안되는 연애

https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 핵심:: MST 기본 문제 풀이:: 처음보고 프림 알고리즘 + 이분 그래프 개념으로 풀어야하나 싶었다. 하지만 간단하게 생각해보면 그냥 양 끝단의 성별이 같은 간선 자체를 제외하면 크루스칼 알고리즘으로 해결 할 수 있다. 의견:: 프림 알고리즘 한번도 구현 안해봐서 풀기 싫었는데 프림 아니었음 프림으로도 구현 자체는 될 거 같다. 시간 복잡도는 만족 시킬지..

[BAE/<JOON> 문제풀이] 2643. 색종이 올려놓기

https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net 핵심:: 색종이 정렬 풀이:: 색종이를 큰 변의 크기 위주로 정렬하고 각 단계에서 윗쪽의 색종이들 중 몇개를 올려놓을 수 있는지 검사한다. 이 때 같은 색종이를 여러번 세게 되므로 (a -> b -> c 순서로 먹힌다면 a -> b 에서 a 한번 (a, b) -> c에서 한번) 이 부분을 중복계산하지 않도록 코딩하면 된다. DP 배열에 해당 번호의 색종이 위에 올려놓을 수 있는 개수..