문제

풀이 방법

개미가 움직이는데 가장 많이 걸리는 시간:max(맨 앞의 개미가 맨뒤로 가서죽기, 맨 뒤의 개미가 맨앞으로가서 죽기)

개미가 움직이는데 가장 짧은 시간 : max(가운데랑 가장 가까운 개미가 맨 앞에서 죽기, 가운데랑 가장 가까운 개미가 맨 뒤에서 죽기)

코드

#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
    int r;
    int *ry;
    int i, j, k;
    k = 0;
    int l, n;
    int *nx;
    int m;
    int d;
    cin >> r;
    ry = new int[r * 2]; //정답을 담는다.

    for (i = 0; i < r; i++) {
        m = 0;
        cin >> l; //length
        cin >> n; //num
        nx = new int[n];
        for (j = 0; j < n; j++)
            cin >> nx[j];
        sort(nx, nx + n);
        for (j = 0; j < n; j++) {
            if(m<min(nx[j], l - nx[j]))
              m = min(nx[j], l - nx[j]);
        }
        ry[k] = m;
        k++;
        ry[k] = max(l - nx[0], nx[n - 1]);
        k++;
    }
    i = 0;
    while(i<r*2){
        cout << ry[i] << " ";
        i++;
        cout << ry[i]<<endl;
        i++;
    }
    return 0;
}

문제

풀이

// bj2217.cpp: 콘솔 응용 프로그램의 진입점을 정의합니다.
//
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    int *p_arr;
    int max =0;
    cin >> n;
    while(n<1 || n>100000)
        cin >> n;
    p_arr = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> p_arr[i];
    }
    sort(p_arr, p_arr + n);

    max = p_arr[n-1];

    for (int i = n-1; i >=0 ; i--) {
        if (max < p_arr[i-1]*(n+1-i))
            max = p_arr[i - 1] * (n + 1 - i);
    }
    cout << max;

    return 0;
}

결과

풀이방법

큰수부터 작은수로 내려가는데, 작은수를 포함했을때와 포함하지 않았을때 이득이 되는지 안되는지를 판단하여 풀이 작성 즉 그리디의 핵심은 로프가 버틸수 있는 중량순이다.

난이도

하

문제 설명

입력으로 사람의 수가 처음 들어가고

그다음줄부터 사람명/사람이 일을 할수 있는 기간 / 보상

이 있다.

이때 보상이 가장 크게 스케줄링 하여라

입력 : 
3
a 1 30
b 1 20
c 3 10

출력 : 
a c

풀이 방법

1.보상이 제일 큰것부터 나열 한 후

2.하나씩 추가하며 적절한지 파악한다.

소스

#include <iostream>
using namespace std;

void exchange(int *arr, int x, int y) {
    int c = arr[x];
    arr[x] = arr[y];
    arr[y] = c;
}

class ATMarr {
private:
    int* m_pArr;
    int m_nVal;
public:
    ATMarr() {

    }
    ATMarr(int val) {
        m_nVal = val;
        while (m_nVal < 1 && m_nVal>1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    ~ATMarr() {
        delete[] m_pArr;
    }
    void SetVal(){
        cin >> m_nVal;
        while (m_nVal < 1 && m_nVal>1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    int GetVal() {
        return m_nVal;
    }
    void SetArr() {
        for (int i = 0; i < m_nVal; i++) {
            cin >> m_pArr[i];
        }
    }

    void printArr() {
        for (int i = 0; i < m_nVal; i++)
            cout << endl << m_pArr[i];
    }

    int Result() {
        int total = 0;
        for (int i = 0; i < m_nVal; i++) {
            total = m_pArr[i] * (m_nVal - i) + total;
        }
        return total;
    }
    void QuickSort(int low, int high) {
        int partitionVal=0;
        if (low < high) {
            partition(low, high, partitionVal);
            QuickSort(low, partitionVal - 1);
            QuickSort(partitionVal + 1, high);
        }
    }
    void partition(int low, int high, int &partitionVal) {
        int lastSmall=low;
        for (int i = low+1; i <= high; i++) {
            if (m_pArr[low] >=  m_pArr[i]) {
                ++lastSmall;
                exchange(m_pArr, i, lastSmall);
            }
        }
        partitionVal = lastSmall;
        exchange(m_pArr, partitionVal, low);
    }

};

int main()
{
    ATMarr ex;
    int val;
    ex.SetVal();
    ex.SetArr();
    val = ex.GetVal();
    ex.QuickSort(0, val-1);
    cout << ex.Result();

    return 0;
}

실수한점

quicksort를 이용하여 배열을 나열하려 하였다.

quicksort에서 
    void partition(int low, int high, int &partitionVal) {
        int lastSmall=low;
        for (int i = low+1; i <= high; i++) {
            if (m_pArr[low] >=  m_pArr[i]) {
                ++lastSmall;
                exchange(m_pArr, i, lastSmall);
            }
        }
        partitionVal = lastSmall;
        exchange(m_pArr, partitionVal, low);
    }

위의 파티션 부분에서 두번 틀렸었다.

1. if (m_pArr[low] >= m_pArr[i]) 이부분에서 >=이렇게 해야 같은 숫자가 나와도 lastSmall을 증가시켜 준다.

2.for (int i = low+1; i <= high; i++) 이렇게 해야 high까지 간다. 예를들어 배열이 5까지 인데 555 1 2 3 4 이렇게 되있을때 1 2 3 4 555 가 되고 그다음 회차에서 partitionVal은 4가 되고 QuickSort(low, partitionVal-1); QuickSort(partitionVal + 1, high); 이 부분에서 (0,3) (5,4) 이런식으로 되어 (0,3에서) 0,1,2만 파티션에서 실행된다.

추가적으로 안 사실

#include의 sort라는 함수가 있다.

#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int arr[5] = { 55,22,33,11,77 };
    sort(arr, arr + 5);
    for (int i = 0; i <= 4; i++) {
        cout << arr[i] << endl;
    }

}

위와같이 써서 quicksort대신 사용하여도 된다.

#include <iostream>
#include <algorithm>
using namespace std;

void exchange(int *arr, int x, int y) {
    int c = arr[x];
    arr[x] = arr[y];
    arr[y] = c;
}

class ATMarr {
private:
    int* m_pArr;
    int m_nVal;
public:
    ATMarr() {

    }
    ATMarr(int val) {
        m_nVal = val;
        while (m_nVal < 1 && m_nVal>1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    ~ATMarr() {
        delete[] m_pArr;
    }
    void SetVal(){
        cin >> m_nVal;
        while (m_nVal < 1 && m_nVal>1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    int GetVal() {
        return m_nVal;
    }
    void SetArr() {
        for (int i = 0; i < m_nVal; i++) {
            cin >> m_pArr[i];
        }
    }

    void printArr() {
        for (int i = 0; i < m_nVal; i++)
            cout << endl << m_pArr[i];
    }

    int Result() {
        int total = 0;
        for (int i = 0; i < m_nVal; i++) {
            total = m_pArr[i] * (m_nVal - i) + total;
        }
        return total;
    }
    void QuickSort(int low, int high) {
        int partitionVal=0;
        if (low < high) {
            partition(low, high, partitionVal);
            QuickSort(low, partitionVal - 1);
            QuickSort(partitionVal + 1, high);
        }
    }
    void partition(int low, int high, int &partitionVal) {
        int lastSmall=low;
        for (int i = low+1; i <= high; i++) {
            if (m_pArr[low] >=  m_pArr[i]) {
                ++lastSmall;
                exchange(m_pArr, i, lastSmall);
            }
        }
        partitionVal = lastSmall;
        exchange(m_pArr, partitionVal, low);
    }
    void Sort() {
        sort(m_pArr, m_pArr + m_nVal);
    }

};

int main()
{
    ATMarr ex;
    int val;
    ex.SetVal();
    ex.SetArr();
    val = ex.GetVal();
    //ex.QuickSort(0, val-1);
    ex.Sort();
    cout << ex.Result();

    return 0;
}

결과