전체 글

[백준] 좌표 압축

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 우선 문제부터 요약해보면, 주어진 좌표들 각각에 대해 총 좌표중 본인보다 작은 것들의 갯수를 출력해야 하는 문제입니다. 이 문제에서 생각 해야 하는 부분들은, 1. 중복된 값이 등장하는 경우에는 하나로 카운팅 해야한다 2. 숫자들이 총 1,000,000개 등장이 가능하기에, 매 숫자마다 전체를 탐색하면 시간초과가 된다 이렇게 두가지입니다. 그래서 ..

[백준] Four Squares

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 우선 문제부터 요약하면, 자연수 n이 주어지면, 해당 숫자를 가장 적은 갯수의 제곱수의 합으로 표현하는 경우 총 몇개가 사용되는지를 출력해야 합니다. 예를 들어서 10이라는 숫자가 있다면, 10에서 1, 4, 9를 뺀 9,6,1 을 만드는 경우의 수중 최소값 + 1이 최솟값이 될 것을 알 수 있습니다. 그래서 이렇게 dp table을 순차적으로 구성해서 계산하면..

[백준] 팩토리얼 0의 개수

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 우선 문제부터 요약해보면, 팩토리얼의 값에서 0이 총 몇개 나오는지를 구하는 문제입니다. 0의 값은 5가 총 몇개 등장하는지를 통해 구할 수 있습니다. N의 값이 500까지 밖에 없으므로, N/5+N/25+N/125의 식으로 쉽게 계산이 가능합니다. 구현은 아래와 같습니다. #include using namespace std; int N; int main(){ cin >> N; cout

[백준] 유기농 배추

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 배추를 재배하는 땅에 배추영역이 총 몇개 존재하는 지를 출력해야 하는 문제입니다. 가장 흔한 유형의 flood fill 유형의 문제이므로 bfs 알고리즘을 접목하여 문제를 해결하면 됩니다. 실제 구현은 아래와 같습니다. #include #include using namespace std; int T, M, N, K; int grid[50][50]; // 0~49 int c, ..

[백준] 에너지 모으기

https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 우선 문제부터 요약하면, N개의 에너지 구슬이 놓여있고, 구슬이 2개 남을 때 까지 한 구슬을 제거하고 그 구슬 양옆의 에너지의 곱을 총 에너지에 더해가는 과정을 반복합니다. 이 때, 최대 에너지를 얼마나 모을 수 있는지를 구해야 하는 문제입니다. 에너지 구슬의 갯수가 많지 않습니다. 그래서 총 경우의 수를 계산해보면 최대 8! 정도 밖에 나오지 않기 때문에 전체를 재귀함수를 통해 구해도 될..

[백준] 두 동전

https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 우선 문제부터 요약하면, N x M의 보드에 빈칸, 벽, 그리고 두 동전이 위치하게 됩니다. 이 때 10번 이하로 두 동전을 같은 방향으로 1칸씩 이동시켜 하나의 동전만 떨어지게 하는 경우가 존재한다면 그 최소 이동횟수를 구하고, 10번 초과 또는 불가능한 경우에는 -1을 출력해야 하는 문제입니다. 10번이라는 조건이 주어졌기 때문에 재귀함수를 이용하여 충분히 구현할 수 있습니다. Return ..

[백준] 부분수열의 합

https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 수열 S가 주어질 때, 해당 수열의 부분수열의 합으로 나올 수 없는 가장 작은 자연수를 구해야 하는 문제입니다. 우선 문제에서 수열의 길이가 20이하로 주어졌기 때문에, dfs로 충분히 해결할 수 있음을 알 수 있습니다. 그리고 각각의 숫자들이 10만 보다 작거나 같다고 했으니, bool canM..

[백준] 부분수열의 합

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열중 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구해야 하는 문제입니다. 정수의 개수가 1~20개라고 문제에서 주어졌으므로 dfs알고리즘을 통해 충분히 해결할 수 있을 것을 알 수 있습니다. 그래서 고르거나 고르지 않거나로 분기하여 dfs를 진행하고, 만약..