PS
BOJ 5557 - 1학년
www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 이 문제는 DP 를 써야 풀 수 있다. 이 문제에 대한 점화식은 다음과 같다 dp[i][j] = k : i 번째 위치에 있는 숫자로 j 가 있을때 (j 의 범위는 0 ~ 20) 가능한 경우의 수 k 문제에서 제시한 예제입력1 을 예로 들면 11 8 3 2 4 8 7 2 4 0 8 8 의 경우, 첫번째 수 8에 대해서는 dp[1][8] = 1 이 성립한다 (첫번째 위치에 들어가는 숫자 8은 경우의 수가 딱..
BOJ 2228 - 구간 나누기
www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 www.acmicpc.net 이 문제는 DP 로 풀어야하는 문제다 규칙을 찾는게 꽤나 어려워서, 시간이 너무 오래걸렸다 그래서 결국 다른 블로그들의 글을 참조했다. DP 배열을 다음과 같이 잡는다 int dp[n][m] : "1 ~ n 번째 인덱스까지의 1차원 배열에서 m 개의 구간을 선택했을때 구간합의 최대값" 이렇게 DP 배열을 잡아주고, -1로 초기화 한뒤, DP 배열을 채우기 위한 재귀함수를 만들어준다 재귀함수의 내부..
BOJ 2212 - 센서
www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1> k; if (k >= n) { // 집중국이 센서 갯수보다 많은경우 예외처리 cout
BOJ 8980 - 택배
www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 골드4라서 그렇게 고난이도는 아닐거라 생각했는데, 꽤나 어려운 문제였다. 처음에는, 출발지를 기준으로 오름차순 정렬해서 박스를 배송해야된다고 생각했는데, 그렇게 될 경우 아래 같은 반례에 막혀서 풀 수 없게 된다. 4 40 3 1 4 40 2 3 40 3 4 40 wrong : 40 correct : 80 출발지를 기준으로 오름차순 정렬하면 1번에서 4번 가고 끝이지만, 더 자세히보면 2 -..
BOJ 1781 - 컵라면
www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 처음에 문제 풀때는 그냥 각 데드라인 마다 최대 값을 골라서 처리하면 될것이라 생각하고 문제를 잘못이해하고 있었다. 예를들면 아래 같은 코드 처럼 더보기 #include using namespace std; int N, answer; vector vec; // 데드라인, 컵라면수 int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> N; int x, y; for ..
BOJ 16562 - 친구비
www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 이 문제는, 유니온 파인드를 써서 푸는 문제이다. 문제에서 주어진 "친구의 친구는 친구다" 라는 문구로 미뤄 봤을때, 같은 집합에 소속된 노드라면, 따로 비용계산을 하지 않아도 된다는 의미가 되기때문에, 유니온 파인드를 써서 동일 집합인지 아닌지 판별하면 되는것임을 의미한다. 그리고 최소 비용으로 전체와 친구가 되야 하므로, 친구비가 더 적게 드는 쪽을 부모 노드로..
BOJ 2933 - 미네랄
www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 처음에 문제 읽었을땐, 클러스터 설명부분에서 많이 헷갈렸는데, 나중에 다시보니 그냥 미네랄 묶음을 클러스터라 칭하고, 막대기 던졌을때, 땅(맨 밑바닥) 과의 간격이 생겨서 공중에 뜨게 된 경우, 밑으로 내려야 하는 그런 문제 였다. 마치 테트리스 블록 내리듯이 막대기를 던지면서, 막대기가 미네랄에 맞게되면, 해당 미네랄은 사라지고, 그 미네랄이 사라짐으로 인해서 생긴 공백을 밑으로 내려줘야한다. 그래서 제일 먼저, 막대기를 ..
BOJ 2589 - 보물섬
www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 전형적인 BFS 문제이다. L 에 해당하는 지역만 탐색하게 하면서, 거리 배열을 따로 만들어둬서, 새 지역으로 이동할때 마다 거리를 갱신해주고, 최대 거리 값을 구하면 되는 문제다. - c++ #include #define MAX 51 using namespace std; char adj[MAX][MAX]; bool visited[MAX][MAX]; int depth[MAX][MAX]; // 거리 계산을 위한 배열..