백준/그리디 (26) 썸네일형 리스트형 백준 2777 - 숫자 놀이 https://www.acmicpc.net/problem/2777 관찰 모든 자릿수의 곱이 N이 되어야 한다. 다시 말하면 N을 만들기 위해 10보다 작은 양의 정수로만 구성되어야 한다. 그리고 N을 만드는 가장 작은 양의 정수 X의 자릿수가 몇개인지 출력하라고 했지 실제 값에는 관심이 없다. 만약 1로만 나눈다고 하면 X는 111111.... 이렇게 무한한 수가 나올 것이다. 즉, 우리는 가장 작은 X를 만들기 위해 가능한 큰 숫자로 나누는 것이 좋음을 발견할 수 있다. 풀이 N을 만드는 가장 작은 X의 자릿수를 구하려면 어떻게 할까? 가장 큰 숫자로 나누는게 좋음을 알았으니 우리가 할 일은 9부터 2까지 반복문을 돌면서 최대한 N을 나누는 것이다. 1은 위처럼 1111... 의 형태가 나와 영원히 끝.. 백준 1493 - 박스 채우기 https://www.acmicpc.net/problem/1493 전략 박스 구석부터 채운다. 가능한 한 가장 큰 박스를 채우도록 한다. 가장 큰 박스를 놓지 않으면 다음과 같은 일이 벌어진다. 위 그림의 빨간 부분처럼 어중간하게 빈 영역이 발생하는데 이런 영역은 모서리에 있는 게 최적이고 그렇지 않으면 큰 큐브가 있어도 끼울 수 없는 경우가 있다. 따라서 이 문제는 큐브를 큰 거부터 채워가는 그리디 문제가 된다. 분할 정복 그러면 구석에서 배치할 수 있는 큰 큐브를 배치했다고 해보자. "다음으로 큰 큐브를 어떻게 배치하는가?"가 관심사가 되는데 배치 가능한 영역을 3~4개로 나누는 방법이 있다. 위처럼 큐브를 채우지 않은 영역을 빨간색, 파란색, 초록색 영역으로 나눌 수 있고 재귀적으로 영역을 나눠가며.. [ICPC] 백준 23248 - Treasure Hunter https://www.acmicpc.net/problem/23248 밑에 적은 풀이는 추가된 데이터로 TLE를 받을 예정이다. 빠른 풀이에 대해선 여기를 참고하라. https://nicotina04.tistory.com/276 LIS와 multiset 사실 이게 뭔진 모르겠지만 나 스스로 뭔가 흥미로운 방법으로 문제를 풀고 있는 것 같아 기록해둔다. 일단 이 문제를 보자. https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠 nicotina04.tistory.com 힌트 더보기 각종 태그에 겁먹지 말자. 이 문제는 set으로 풀 수 있으며 본인도 본 대회에서 set으로 AC를 받았다. 로봇이 갈 수 있는 방향에 근거하여 X들을 서로 이어보자. .. [ICPC] 백준 11501 - 주식 https://www.acmicpc.net/problem/11501 힌트(시간 초과 관련) 더보기 이 문제는 $O(N)$으로 풀 수 있다. 당신은 이미 계산했던 날을 다시 거쳐갈 필요가 없음을 상기하라. 풀이 더보기 각 날마다 주식의 가격이 주어졌을 때 최대 이득을 취하는 방법을 찾아야 한다. 우리는 이미 어느 날에 가격이 높은지 알고 있다. 다음 개형을 보자. 이런 형태에서는 1~2일에 매수하고 3일에 매도, 4~5일에 매수하고 6일에 매도하는 게 최적해가 됨을 단박에 알 수 있다. 다음 개형도 보자. 이런 경우는 1~5일까지 매수를 하다가 6일에 전부 매도하는 게 최적해가 된다. 이 두 개형을 통해 우리는 주식 가격의 극대 값에 도달하기 전까지 매수를 해야 함을 발견할 수 있다. 그렇다면 이를 어떻게.. 백준 1439 - 뒤집기 https://www.acmicpc.net/problem/1439 힌트 더보기 1로 만들기 vs 0으로 만들기 둘 중 최소가 되는 횟수가 최적해이다. 풀이 더보기 모든 수를 1로 만들거나 0으로 만들어야 한다. 어떻게 하면 최소가 될 수 있는지 알 수 있을까? 문제에서 이야기한 전체를 뒤집는 것은 사실 의미 없는 행동이다. 문자열에서 0의 묶음 개수를 x, 1의 묶음 개수를 y라고 할 때 전체를 뒤집으면 x랑 y의 값이 서로 뒤바뀔 뿐이기 때문이다. 그러면 우리는 각 묶음의 개수 중 최소가 바로 정답이 됨을 깨달을 수 있다. 구현의 편의를 위해 erase를 사용하여 중복 문자열을 없애버린 뒤 0과 1이 나타나는 횟수를 각각 세서 그중 최소를 출력하면 된다. 전체 코드 #include using names.. 이전 1 2 3 4 5 6 다음
