백준 9095, 10819

<9095 - www.acmicpc.net/problem/9095>

#include <iostream>
int arr[11];
int n;
int function(){
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;
    for(int i = 4; i <= n; i++){
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
    }
    return arr[n];
}

int main(){
    int T;
    scanf("%d", &T);

    for(int i = 0; i < T; i++){
        scanf("%d", &n);
        printf("%d \n", function());
    }
    return 0;
}

- \n 안붙였다고 한번 틀렸다.

- 5는 4+1로 나누어지고 4는 또 2+2, 3+1등으로 나뉘는걸 이용해 점화식으로 문제 해결

- 입력을 모두 끝낸 후 출력을 하려면 배열을 또 만들어야 하는데 자료구조적으로 좋지 못하다.

    - 테스트할 갯수 입력 > 입력 > 출력 > 입력 > 출력 ...... 이 더 메모리 낭비가 없다

 

<10819 - www.acmicpc.net/problem/10819>

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

int main(){
    int N, result;
    int arr[8];

    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%d", &arr[i]);

    sort(arr, arr+N);          // algorithm에 있는 정렬

    // ([0] -[1]) + ([1]-[2]) ... 이런 식의 식을 다 해보면 된다
    do {
       int sum = 0;     // 초기화 안하면 값이 누적된다
       for(int i = 0; i < N-1; i++) {
        sum += abs(arr[i]-arr[i+1]);
       }
       result = max(result, sum);
    } while (next_permutation(arr, arr+N)); //배열 모든 원소로 순열을 만들때 까지

    printf("%d\n", result);
}

- 잘 되는데 틀렸다 한 코드

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

int main(){
    int N, result = 0;
    int arr[8];

    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%d", &arr[i]);

    sort(arr, arr+N);          // algorithm에 있는 정렬

    do {
       int sum = 0;     // 초기화 안하면 값이 누적
       for(int i = 0; i < N-1; i++) {
        sum += abs(arr[i] - arr[i+1]);
       }
       result = max(result, sum);
    } while (next_permutation(arr, arr+N)); //배열 모든 원소로 순열을 만들때 까지

    printf("%d\n", result);
}

- 는 사실 result 초기화 안해서였구요

- 에디터에서는 result 초기화 없이도 잘 해결을 했는데 백준에서는 아닌가보다. 다음에는 초기화 더 잘 보자

 

- next_Permutation은 자료구조에서 배운 C++의 STL인데 지정해둔 배열의 범위로 순열을 전부 만든다고 생각하면 된다

    - 만약 next_Permutation( 1, 3 ) 이라고 하면 1,2,3 > 1,3,2 > ... > 3,2,1 > 1,2,3 (처음이랑 같으니 false반환) 의 작업을 하는 것이다

    - 순열을 전부 만들고 나서 false를 반환하니 조건문에 넣어 사용하기 좋다

    - C++ 만세