https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 오랜만의 Dynamic Programming이라서 헤맸다. 처음에는 당연히 모든 경우의 수를 세볼까 했는데, 2와 3의 개수가 1의 개수에 의지하는 듯한 느낌이 든다. 그래서 논리적으로 접근하기 시작하면 전형적인 다이나믹 프로그래밍이다. 만약 정수 4를 합으로 나타내고, 중복은 제거하기 때문에 가장 큰 수를 앞에 둔다면 - 1로 시작하..

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 전형적인 최소 거리 찾는 알고리즘이고, 플로이드 와샬과 다익스트라 알고리즘 중 다익스트라 알고리즘을 선택하면 된다. 왜냐하면 출발점과 도착점이 각각 하나씩 정해져있기 때문이다. 그런데 구현 과정에서 자꾸 반복적으로 Queue의 내부 자료구조에 임의의 점과 해당 점까지의 출발점으로부터의 거리를 pair를 써서 같이 넣으려고 하는데, 그럴 필요가 없다!!!! 왜냐하면 dist라는 배열에 가장 최신의 거리를 기..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 앞서 푼 문제는 쉽게 문제를 접근해서 풀었다면, 이번에는 단순히 쉽게 접근하면 시간 초과로 풀 수 없다. 탑을 하나씩 접근하면서($O(N)$), 각 탑의 앞 탑들을 탐색하면 전체적으로 $O(N^2)$ 의 시간 복잡도가 나온다. 여기서 누적합으로 풀어야 하나 고민했지만 탑의 길이가 지나치게 길다는 점부터 고려의 대상에서 제외하였다. 효율적인 풀이를 고민하던 끝에 왜 탑을 순서대로 탐색하는 게 비효..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 진짜 울고 싶다 으헝헝 8ㅅ8 아무리 풀어도 제대로 못 푼다...심지어 이거 골드5인데.. 계속 꼬인다.. 문제를 쉽게 풀어내도록 접근했어야 했는데 괜히 이중 for문을 쓰면서 어렵게 풀려고 했다. 최대한 간결하고 쉽게 풀 생각을 우선 해야할 것 같다. 빗물이 쌓이는 구간을 이중 for문으로 구하려 했는데, 이렇게 되면 예외가 많이 생기고 복잡해진다. 대신 한 점씩 각각 for문..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 삼성 코딩테스트 연습하기에 좋았던 시뮬레이션 & 탐색 문제이다. 평소에 DFS를 할 때 자주 inside 함수를 생성하는 것을 잊는다. 실수하지 말아야 한다. 그리고 해당 문제는 반복되는 일련의 과정 속에서 연합을 따로 구해서 처리를 해야 하는데, 그 때 연합끼리의 정보가 서로 침법하지 ㅇ낳도록 주의해야 한다. 여기선 한 연합에서 이미 인구 수를 조정한 것이 다음 연합에 영향을 주어..

https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 간단히 말하자면 빨간 볼, 파란 볼 분리 문제이다. 크게 결과의 경우의 수는 4가지 이다. 1. 빨간 볼을 움직여서 오른쪽으로 모은다. 2. 빨간 볼을 움직여서 왼쪽으로 모은다. 3. 파란 볼을 움직여서 오른쪽으로 모은다. 4. 파란 볼을 움직여서 왼쪽으로 모은다. 그런데 여기서 더 나아가서 어떤 게 효율적일지 고민해보면 어차피 끝에 이왕 모여 있는 볼들을 활용하면 좋..