돌이 코딩하는 방

문제 태그 : https://www.acmicpc.net/problem/18292 문제 소개 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. 문제 풀이 숫자가 작고 인접한 칸을 고르지 않는다는 조건. Bit를 활용한 DP가 풀이로 바로 떠오른다. 한 줄에 대해서 0~2^m 까지를 고르는 경우를 모두 고려 해주면 된다. 각 숫자별로 켜져 있는 비트가 골라진 칸 이라고 생각하면 된다. dp[i][j][k]= i 번째 줄까지 j 개의 칸을 선택했으며, 마지막 (i번째) 줄 의 선택된 모양이 k일때 최댓값이다. 총 테이블의 크기는 O(NK 2^M)이고, ..

USACO 2017 January Contest에 대한 전체 풀이를 작성하려고 한다. Bronze ~Gold 까지는 전부 작성하고 Platinum은 되는대로 추가할 예정이다. 백준에서는 https://www.acmicpc.net/category/395에서 볼 수 있다. Bronze 1 BOJ 14455 Don't Be Last 문제 설명: 우유를 얻은 소와 양이 여러차례에 걸쳐 주어질 때 마지막에서 두번째로 적은 양의 우유를 얻은 소를 구하시오. 문제 풀이: 구조체등을 이용하여 이름과 우유의 양을 같이 저장하자. 이름에 맞춰 짠 우유의 양을 더해주고, 정렬을 해서 출력하면 된다. 여담: 다른 브론즈 문제보다 오히려 어려웠다. 구현과정에서 고려해야 할 것이 적지 않고 은근히 까다로운 문제. Bronze 2..

문제 태그 : https://www.acmicpc.net/problem/17955 나한테 잘 맞는 문제였다. 정말 좋은 문제라고 생각한다. 문제 소개 n,m이 주어진다. 이후 1 이상 m 이하의 수 n개가 주어진다. n개의 숫자는 원형으로 이루어져 있다. 이후 2가지 행동을 할 수 있다. 1. 어떤 한 칸을 골라 그 수를 max(원래 숫자, 왼쪽의 숫자, 오른쪽 숫자)로 바꾼다. 2. 어떤 한 칸을 골라 그 수를 min(원래 숫자, 왼쪽의 숫자, 오른쪽 숫자)로 바꾼다. 원형으로 이루어진 n개의 숫자를 모두 (1,2,3,...m)으로 만드는데 필요한 최소 행동의 횟수를 각각 구하시오. 만약 만들 수 없다면 -1을 출력한다. 문제 풀이 스포 주의! Step1. 문제 관찰 문제의 예제를 봄으로써 몇가지 사실..

문제 태그 : https://www.acmicpc.net/problem/1006 앞에서 순서대로 푸는 사람들이 절망할만한 문제이다. 1000~1005 보단 확실히 난이도가 있다. 문제 설명 원형 2열로 배치된 2n 개의 칸을 최소 그룹의 갯수로 묶어야 한다. 그룹에는 조건이 있다. 최대 2개가 같은 그룹일 수 있으며, 배치 상에서 연속된 칸이어야 하고, 두 칸의 값의 합이 m을 넘지 않아야 한다. 2칸이 한 줄이고 n줄이 있다고 생각하면 된다. 문제 풀이 DP를 쓰고 싶은 느낌이 들었다. 어떤 줄까지 다 채우는데 사용된 최소 그룹의 갯수를 이용해 다음 줄까지 채우는데 사용된 최소 그룹의 갯수에 영향을 준다고 생각할 수 있기 때문이다. 하지만 문제가 있다. 어떤 칸을 채울 때에는 이전 칸을 완벽히 채운 상..

USACO 2018 February Gold 3번이다. BOJ 15747번에 등록되어 있으며 문제는 여기서 볼 수 있다. 문제 설명 문제해석과 이해가 굉장히 어려운 문제다. N이 주어지고 우리는 총 N개를 k개의 그룹으로 나눠야 한다. 이때 나눈 그룹별로 숫자가 0부터 1씩 올라가며 부여된다. 예를 들어 9를 4 3 2로 분할 했다면, (0,1,2,3)(0,1,2)(0,1)이 된다. 이때 분할 후에 매겨진 값으로 만들어진 배열이 주어진 배열과 최소 몇 개가 다른지 n 이하의 모든 k에 대해서 출력해야 한다. 예제를 예시로 들자면 1개의 그룹은 무조건 0,1,2,3,4,5로 1,2 만 같습니다. 2개의 그룹으로 나눌 때는 0,1,2,3 0,1 로 나누어야 다른 원소가 2개로 가장 적습니다. 3개의 그룹으로..

문제 태그 : https://www.acmicpc.net/problem/1520 문제 설명 문제 풀이 (사고의 흐름) (1,1)에서 (n,m)으로 갈 수 있는 경우의 수 찾기. 경우의 수를 찾는 것이고, 어떤 칸까지 갈 수 있는 경우의 수는 그 칸으로 올 수 있는 경우의 수의 합으로 표현된다. 따라서 이 문제는 2차원 DP로 해결 할 수 있다. 2차원 필드에서 진행되는 보통의 간단한 DP 문제 같은 경우에는 오른쪽 혹은 아래로 밖에 움직이지 못한다. 따라서 (i,j)는 (i-1,j)와 (i,j-1)로 표현이 된다. 하지만 이 문제는 그렇지 않다. 어떤 (i,j)의 칸으로 올 수 있는 칸은 주위의 4칸 중 (i,j)보다 숫자가 큰 칸이다. 따라서 (i,j)에 대한 경우의 수를 확실하게 구하기 위해서는 주변..

USACO 2018 US Open Gold 2번이다. BOJ 15758번에 등록되어 있으며 문제는 여기서 볼 수 있다. 문제 설명 첫 줄에 n과 m이 주어진다. n는 소의 숫자이며, m은 세트의 숫자이다. 다음 m개의 줄에 한 세트씩 입력이 들어온다. 한개의 세트에 대한 입력은 k와 k개의 숫자로 구성된다. k개의 숫자는 소들의 순서관계이다. 우리는 위에서부터 최대한 많이 순서를 지켜서 소들을 정렬 시키려고 한다. 순서가 상관없는 소들에 대해서는 숫자가 작은 소를 우선으로 정렬한다. 이때 위에서 부터 지킬 수 있는 조건의 갯수와 그 정렬방법을 출력해야 한다. 문제 풀이 문제를 보자 마자 바로 떠오르는 개념이 있다. "위상정렬". 위에서 부터 최대 몇 개까지의 조건을 지킬 수 있는지를 알 수 있다면 Pri..

문제 태그 : https://www.acmicpc.net/problem/4243 문제 설명 문제 풀이 (사고의 흐름) 일단 DP라는 것을 어느정도 바로 생각할 수 있었다. 직선에서 하는 DP인데 N이 작기 때문에 N^2이라고 생각을 했고, 이러면 보통 DP[i][j]는 i에서 j까지 ~~~ 라고 생각했다. 여기서 우리는 i 부터 j까지 다 들렀다면 당연히 최종위치는 i또는 j라는 것을 알 수 있다. 들르는데 걸리는 시간은 0이기 때문에 중간에 띄고 건널 이유가 아예없다. 그래서 관찰한 사실을 토대로 DP[state][i][j]는 state의 방향에 있으면서 i부터 j까지 들리는데 기다림의 합의 최소라고 생각할 수 있다. 하지만 이러면 문제가 있다. 지금까지 대기시간의 총합이 최소가 되는 경우가 지금까지 ..

문제 태그 : https://www.acmicpc.net/problem/1848 다익스트라에 관해 포스팅을 하다가 백준 다익스트라 문제들을 살펴보았는데, 한 문제 시도하다가 틀린 흔적을 발견했다. 그래서 그 문제를 풀게 되었는데, 굉장히 좋다고 생각하여, 풀이도 저장할겸 포스팅을 하게 되었다. 문제 설명 양 방향 그래프가 주어지는데 일반적인 양방향 그래프와 다른 점은 A점에서 B점으로 갈 때의 비용과 B점에서 A점으로 갈 때의 비용이 다르다는 것이다. 이때 목적은 1번 정점에서 출발하여 1번 정점으로 다시 돌아오는 최단거리를 구하는 것이다. 이때 한 번 지난 간선은 역으로도 다시 올 수 없다는 것이다. 즉 다시 말해, 1->3->1의 경로로 이동하는 것은 안된다는 것이다. 문제 풀이 (사고의 흐름) 일단..

문제 태그 : https://www.acmicpc.net/problem/1753 문제 설명 이 문제에서 요구하는 것은 방향그래프에서 특정 정점이 주어졌을 때 그 점으로부터 모든 점까지의 거리를 각각 구하는 것이다. 이는 다익스트라 알고리즘이 하는 일과 정확히 일치한다. 맞다. 다익스트라를 한번 연습해보라는 뜻이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include using namespace std; typedef long long int ll; typedef pair pii; #define ff first #define ss..