https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 추의 개수와 각 추의 무게가 주어졌을 때, 주어진 추들을 양팔 저울에 올려 측정할 수 있는 무게의 종류를 구하는 문제이다. 추를 양팔 저울의 한 쪽에만 올리는 경우와 다른 반대쪽에도 올릴 수 있는 경우가 있다는 점이 이 문제의 어려운 점이다. 측정하려는 무게를 x, 현재 사용하는 추의 무게를 w, 이전까지 측정한 적 있던 무게를 p 라고 하자. 그렇다면 측정하려는 무게를 양팔저울의 왼쪽에 놓았을 때..
https://www.acmicpc.net/problem/1796 1796번: 신기한 키보드 동혁이의 키보드에는 버튼 세 개와 LCD창 한 개가 달려 있다. LCD창에는 문자열 S가 쓰여 있다. 그리고 커서는 문자열의 가장 왼쪽 글자에 위치해 있다. 버튼 세 개는 왼쪽, 오른쪽, 엔터키이다. 왼 www.acmicpc.net 옛날에 봤을 땐 분명 골드5 문제였는데 어느샌가 골드4로 올라간 문제이다. 풀고나서 보니까 왜 누구는 골드5로, 누구는 실버1로 매겼는지 알 것 같았다. 문제 상황을 프로그래밍적으로? 정의하고 나면 되게 간단해지기 때문이다. 그런데 이 문제는 그 정의가 어려운 문제였다 그래서 나도 이 문제 난이도에 골드4를 줬다. 문제는 간단하다. 좌우버튼과 엔터 버튼만으로 구성된 키보드를 이용해 주..
https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 처음엔 그림만 보고 그래프 문제를 예상했는데, 문제를 읽어보니 경우의 수를 세라길래 DP로 예상해서 DP 점화식을 세웠다. 근데 dp테이블을 일일히 채우고 있다가는 저 10억이라는 입력데이터를 감당하지 못하겠다는 생각이 들었다. 그래서 결국 알고리즘 분류를 봤다.. 그런데 띠용.. '분할정복을 이용한 거듭제곱' 문제라고 소개가 되어있었다. 다행히 이걸 보고 전에 풀었던 피보나치 문제가 스쳐지나갔다. 행렬 거듭제곱을 이용해서 피보나치 수열을 빠르게 구하는 문제였다. 그런데 부끄럽게도 그 문제를 풀 당시에는 피보나치..
https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 쓸데없이 힘들게 푼 문제이다. 알고리즘 분류가 백트래킹에 브루트포스였는데, 그렇게 풀었으면 더 쉽게 풀었을 것 같다. 전체 경우의 수가 1023가지 밖에 되지 않아서, 그냥 모든 케이스를 순서대로 방문해보면 된다. 각 숫자가 중복으로 쓰일 수 없어서 비트마스킹을 활용한 풀이도 있었다. 나는 DP 에 역추적을 써서 풀었다. 정말 빙빙 돌아서 풀었다 ㅋㅋㅋ 내가 푼 풀이는 2차원 DP ..
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 간만에 만난 진짜 너무 이해하기 어려웠던 문제이다. 이 문제를 풀고 이해하는데 3시간이 걸렸다 (이래야 골드1이지..) 이 문제의 핵심은 3가지다. 1. 최적해는 결국 사이클이기 때문에 어디에서 시작점을 잡아도 좋다. 2. 지금까지의 누적된 값에 내 값을 더해주는게 아니라, 누적될 값을 넘긴다. 3. 최소를 구할 때도 0을 조심하자. 1. 최적해는 결국 사이클..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 난이도에 비해 티어가 높게 책정되었다고 생각하는 문제이다. (그리고 나와 똑같이 생각한 사람이 꽤 되는 것 같다.) 펠린드롬 문자열의 성질을 이용하면 아주 간단하게 풀 수 있다. 어떤 문자열이 펠린드롬이면, 그 문자열의 양끝 문자를 제외한 문자도 펠린드롬이다. 따라서 dp[s][e] 를 s 부터 e 까지의 문자열의 펠린드롬 길이라고 한다면 dp[s][e] = dp[s+1][e-1] + 2 이다. 단, 위 점화식의 조건은 dp[s+1][..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 스티커 문제를 발전 시킨다면 이 파이프 옮기기 문제가 될 것 같다. 좋은 DP 연습문제이다. 처음에는 당연히 BFS를 이용해서 풀어야겠다고 생각했는데, BFS로는 최단경로를 찾아보기만 했지, 최단경로의 '개수'를 세어보진 않아서 백준님의 표현을 빌리자면, BFS의 형태를 모방한 브루트포스 풀이로 밖에 짜지지가 않았다. (그리고 이 방식은 당연하게도 시간초과를 받는다..) ..
문제 소개 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 가장 긴 증가하는 부분 수열의 응용문제이다. 가장 긴 증가하는 부분 수열의 풀이 과정을 정확하게 이해하고 있다면, 이 문제 역시 어렵지 않게 풀 수 있다. (골드3 난이도길래 특별한 코너케이스가 숨어있는 줄 알았는데, 다행히 그런 건 없었다.) 11053 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 9465 스티커 https://www.acmicpc.ne..
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 그래프 문제를 풀고 싶어서, solved.ac의 그래프 태그 문제를 찾아보다가 발견한 문제이다. 스타크래프트를 연상시키는 문제인데, 그래프에 DP를 섞은 재미있는 문제였다. 우선 이 문제는 문제에서 주어진대로 시작하는 건물부터 차근 차근 건물을 지어나가다가 마지막에 원하는 건물을 짓게되면 멈추는 풀이로는 접근이 쉽지가 않다. 그래서 거꾸로 원하는 건물을 짓기 위해 지어야 하는 건물들을 역탐색..
