[0529] 알고리즘

  어쩌다 보니 알고리즘 공부를 하게 되어서(?) 푼 문제 있음 백업 겸 올리기로 한다...

 

---

2156. 포도주 시식

  과제로도 한 번 받은 적 있는 거라서 복습 겸 코딩 재활겸(...) 과제의 추억을 떠올리며 진행.

  다이내믹 프로그래밍을 사용하는 문제였고, 과제로 받았을 땐 Top-down 형식으로 할 것이 조건이었기 때문에 이번에도 그렇게 했다. 과제로 했을 때는 수학을 하도 못해서 손으로 직접 경우의 수를 따져가며(...) 어떤 조합으로 해가 나올 수 있는지 하나하나 따지면서 풀었었음.

 

#include <iostream>

int divideGlass(int num, int* glasses);
int divideGlassAux(int num, int* m, int* glasses);
int compareMax(int a, int b, int c);

int main()
{
    int num = 0; //총 잔 수
    
    std::cin >> num;

    int * glasses = new int[num]; //각 포도주 잔의 양

    for (int i = 0; i < num; i++)
    {
        std::cin >> glasses[i];
    }

    int max = 0;

    max = divideGlass(num, glasses);

    std::cout << max;

    //메모리 해제
    delete[] glasses;
}

int divideGlass(int num, int * glasses) {
    int * memory = new int[num + 1];

    for (int i = 0; i < num + 1; i++) memory[i] = -1; //기억 배열 초기화

    return divideGlassAux(num, memory, glasses);
}

int divideGlassAux(int num, int* m, int * glasses)
{
    if (num == 0) m[0] = 0;
    if (num == 1) m[1] = glasses[0];
    if (num == 2) m[2] = glasses[0] + glasses[1];

    if (m[num] >= 0) return m[num];
    else
    {
        m[num] = compareMax(divideGlassAux(num - 1, m, glasses), divideGlassAux(num - 2, m, glasses) + glasses[num - 1], divideGlassAux(num - 3, m, glasses) + glasses[num - 2] + glasses[num - 1]);
        return m[num];
    }
}

int compareMax(int a, int b, int c)
{
    if (a >= b && a >= c) return a;
    else if (b >= a && b >= c) return b;
    else return c;
}

  재귀를 이용하되, 이미 구한 값은 memory 배열에 저장하여 재활용하는 방식.

 

  알고리즘 문제 제대로 풀어본 게 해당 과목 들었을 때 밖에 없어서(...) 이런 문제 코드를 어떤 식으로 짜야하는지 모르겠다. 일단 과제 때 진행했던 대로 풀었음... 다이내믹 프로그래밍 기억이 드문드문해서 강의자료 뒤져가며 했더니 정신이 하나도 없다.

 

---

새로 알게 된 팁?

 

• https://www.acmicpc.net/board/view/22716

글 읽기 - 추가 설명 및 다른 언어 빠른 입출력 방법

 

  n년 전에 풀다 만 단계별로 풀어보기에서 쉬운 브론즈 문제들 풀어놔야지~ 하다가 발견한 글.

  C++을 사용하려고 마음 먹은 지(+공부한지) 얼마 안 되어서 처음 안 사실인데, cin와 cout의 사용은 속도에 영향을 준다는 듯 싶다. 해서, cin와 cout을 좀 더 빠르게 사용하기 위해 쓰는 코드가 존재한다는 듯.

 

- std::cin.tie(NULL);

  cin와 cout의 묶음을 푼다. cin으로 읽기 작업을 수행할 땐 출력 버퍼를 비우는 작업을 먼저 수행하기에 이를 분리하기 위한 과정인듯. 입출력이 잦다면 필수적이라고.

 

- std::ios::sync_with_stdio(false);

  C와 C++의 버퍼를 분리한다. 단, 이를 사용하면 C의 scanf, getchar 등의 사용이 불가능해진다고. 해당 함수를 쓸 때는 사용하지 않도록 하기.

 

---

 

  C++도 제대로 할 줄 몰라서 거의 C랑 다를바 없이 쓰고 있는데... 빨리 벡터같은 것도 익혀서 써먹어보던가 해야지 아이고