그리디11 AtCoder ABC 265 풀이 A. 1개살때 X원, 3개살때 Y원이 들때 N개살때 최소비용을 구하는 문제입니다. 우선, Y가 3X이상이면 그냥 다 1개씩 사면 됩니다. 그 외의 경우엔 3개씩 최대한 묶고 남은걸 1개씩 사주면 됩니다. #include using namespace std; int main() { ios::sync_with_stdio(0), cin.tie(0); int x, y, N; cin >> x >> y >> N; if (y >= 3 * x) { cout n >> m >> t; for (int i = 1; i > a[i]; psum[i + 1] = psum[i] + a[i]; } ll time_limit = t; x[0] = 1; for (int i = 1; i > x[i] >> y[i.. 2022. 8. 25. 백준 1493 / C++ https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net [ 풀이 ] 큐브들은 모두 작은걸로 큰걸 채울 수 있다. 따라서 그리디하게 길이에 맞는 가장 큰 큐브부터 사용하면 된다. (각 큐브가 작은것으로 큰걸 채우지 못하면 그리디를 사용할 수 없다.) 큐브를 사용했다면 박스는 세 부분으로 나뉜다. 이제 이 세부분으로 divide&conquer 해주면 된다. [ Code ] #include using namespace st.. 2022. 8. 12. 백준 2873 / C++ https://www.acmicpc.net/problem/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net [ 풀이 ] 홀수인 변이 있다면 전부 방문할 수 있음은 자명하다. 모두 짝수인 경우의 문제를 풀자. 규칙을 찾아보자. 전부 방문하는건 불가능하다. 증명은 다음과 같다. 전부 방문하려면 (r-1)(c-1)개의 화살표가 필요하다. 이 값은 홀수이다. 그런데 시작점에서 끝점으로 가는데엔 짝수번의 화살표가 필요하다. 따라서 홀짝성에 위배된다. 그럼 되도록 1개만 제외하고 방문하고 싶다. 이런 문제의 .. 2022. 8. 12. 백준 21761 / C++ https://www.acmicpc.net/problem/21761 21761번: 초직사각형 1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자. 선분의 크기는 변수 $A$로, 직사각형의 크기는 두 개의 변수 $A$와 $B$로, 직육면체의 크기는 세 개 www.acmicpc.net [ 풀이 ] 부피 ABCD에서 한 변을 증가시키면 (A+U)BCD가 된다. 그럼 매번 변화시키면서 1+U/A가 커지도록 해주면 된다. 그리디하게 매번 A,B,C,D중 제일 큰 U를 뽑아서 1+U/x가 제일 큰걸 매번 뽑아주면 된다. 기존 ABCD에서 이렇게 가장 큰 비율을 매번 곱해줘야 최대가 되는건 자명하다. 그 비율이 1보다 크기 때문에 항상 값이 커지기 때문이다. 매번 제일 큰 .. 2022. 8. 8. 이전 1 2 3 다음