JArchive 프로그래밍 일기

문제

카드 구매하기 백준 11052번

리뷰

유념해야 할 것은 카드 i개 들어있는 카드팩 가격이 P[i] 원 이라는 것이다.

점화식을 세우는 게 쉽지 않았다.

입력받은 카드팩 가격 배열 P[i]와 i장 샀을 때 최대값을 기억하는 배열 M[i]를 사용한다.

예제 입력 n = 4 , P[i] = [1, 5, 6, 7] 일 때, 예제 출력은 10이다.

카드 a 장을 살 때 최대 지불하는 금액을 배열 M[a] 에 넣고, 최종 답 M[n]을 구한다.

M[1] = max(P[1], M[1])

M[2] = max(M[1] + P[1] , M[2])

i = 5 인 경우,

M[1] + P[4], M[2] + P[3], M[3] + P[2] , M[4]+P[1] 인 경우를 비교해야 한다. -> 2중 for문

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

// 카드 구매하기  (BOJ 11052) 

vector<int> P(10001);
int max_value[1001];

int main(void){

    freopen("input.txt", "rt", stdin);

    int n = 0, num = 0;
    int i = 0, j = 0;

    scanf("%d", &n);

    for(i = 1; i <= n; i++){
        scanf("%d", &num);
        P[i] = num;
    } // 카드팩 n개의 값을 입력받는다. 

    for(i = 1; i <= n; i++){

        for(j = 1; j <= i; j++){ //   

            max_value[i] = max(max_value[i-j] + P[j], max_value[i]);

        }
    }

    printf("%d", max_value[n]);

    return 0;
}

문제

2xn 타일링2 백준 11727번

리뷰

2xn 타일링 문제를 풀고 연이어 풀었다.

n이 1, 2, 3, 4 일 때 어떤 경우가 나오는지 그림을 그려보니까 규칙성을 발견할 수 있었다.

계속 숫자를 더하다보면 자료형의 크기를 넘을 수 있다는 힌트를 유념하면서 배열에 숫자를 저장하기 전에 mod 연산을 해줬다.

코드

#include <stdio.h>
using namespace std;

// 2xn 타일링2 (백준 11727) 
int arr[1001];

int main(void){

    int i = 0, n = 0;
    scanf("%d", &n);

    arr[1] = 1;
    arr[2] = 3;
    arr[3] = 5;

    for(i = 4; i <= n; i++){
        arr[i] = (arr[i-2] * 2 + arr[i-1]) % 10007;
    }

    printf("%d", arr[n]);

    return 0;
}

문제

2xn 타일링 백준 11726번

리뷰

피보나치 수열과 비슷한 문제여서, 점화식은 만들었는데 계속 틀렸다.

문제 해설 포스팅을 구글링 해보니, 계속 숫자를 더하다보면 자료형의 크기를 넘을 수 있다는 힌트를 발견했다.

그래서 배열에 숫자를 저장하기 전에 mod 연산을 해줬다.

왜냐하면 결국 답은 mod 연산 결과이기 때문이다.

코드

#include <stdio.h>
using namespace std;

// 2xn 타일링 (백준 11726) 

int arr[1001]; 

int main(void){

    int n = 0;
    int i = 0;

    //freopen("input.txt", "rt", stdin);

    scanf("%d", &n);

    arr[1] = 1;
    arr[2] = 2;

    for(i = 3; i <= n; i++){

        arr[i] = (arr[i-1] + arr[i-2]) % 10007;

    }

    printf("%d", arr[n]);

    return 0;
}

참고 포스팅

문제

분산처리 백준 1009번

리뷰

제곱을 했을 때 가장 마지막 자리의 숫자가 뭔지 출력하면 되는 문제다.

b의 입력 조건이 큰 것을 감안해야 한다.

제곱을 하는 와중에도 '마지막 자리 수'만 잘라내서 제곱을 해야 int 범위를 넘지 않는다.

그래서 temp = temp * a 이렇게 제곱을 한 다음에 %10 나머지 연산을 통해 마지막 숫자를 잘라냈다.

for(i = 2; i <=b; i++){
    temp = temp * a % 10; // 마지막 자리 숫자 잘라내기 
}

이렇게 해도 자꾸 '틀렸습니다' 가 뜨길래 문제 해설 포스팅을 찾아봤다.

힌트는 제곱을 했을 때 4번 주기로 같은 숫자가 나온다는 것이었다.
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 6 (마지막 자리 숫자만 씀)
2^5 = 2
2^6 = 4

이렇게 2, 4, 6, 8 이 반복된다.

(4번째 제곱수마다 마지막 자리숫자들이 똑같이 반복되는 것을 이용한다. )

그래서 제곱 횟수 b를 % 4 연산을 했고, b가 0이 되는 것을 방지하기 위해 + 4를 해준 것이다.

b = b % 4 + 4; 

제곱횟수 b를 mod 연산을 하니까 그제서야 문제를 맞혔다. 아 개운하다 다음에 다시풀어봐야지 :)

코드

#include <stdio.h>
using namespace std;

// 분산처리 (BOJ 1009번) 

int main(void){

    //freopen("input.txt", "rt", stdin);

    int tc = 0, a = 0, b = 0;
    int temp = 0, i = 0; 

    scanf("%d", &tc);

    while(tc--){
        scanf("%d %d", &a, &b);

        temp = a;

        b = b % 4 + 4;  // b가 0이 되는 것을 방지하려고 +4 한다. 

        for(i = 2; i <= b; i++){ // 마지막 자리 숫자만 잘라낸다 
            temp = temp * a % 10;
        }

        if(temp == 0)
            temp=10;

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

    return 0;
}

참고 포스팅

크레이 님의 분산처리 문제 해설

크레이 님의 친절한 포스팅 감사합니다! :)

문제

스택 백준 10828번

리뷰

C++ STL stack에 구현된 함수들과 으로 금방 풀 수 있었다.

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

// 스택 (BOJ 10828번)  

int main(void){

    int order = 0, i = 0; 
    int num = 0;
    stack<int> st;
    string input = "";

    freopen("input.txt", "rt", stdin);

    scanf("%d", &order);

    for(i=0; i<order; i++){

        cin >> input;

        if(input == "push"){ 

            scanf("%d", &num);
            st.push(num);

        }else if(input == "pop"){

            if(!st.empty()){
                num = st.top();
                st.pop();
            }else{
                num = -1;
            }
            printf("%d\n", num);

        }else if(input == "top"){

            if(!st.empty()){
                num = st.top();
            }else{
                num = -1;
            }

            printf("%d\n", num);

        }else if(input == "size"){
            printf("%d\n", st.size());

        }else if(input == "empty"){
            printf("%d\n", st.empty());
        }

    }

    return 0;
}

백준 괄호 문제 풀이  https://www.acmicpc.net/problem/9012

닫는 괄호로 시작하는 경우에 어떻게 할지 예외처리를 안넣어줘서 시간이 좀 걸렸다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>

using namespace std;

void check() {
	char stack[50] = {0, };
	int stack_idx = 0;

	char* inputStr = (char*)malloc(sizeof(char) * 50);
	scanf("%s", inputStr);

	int lenSize = strlen(inputStr);

	for (int i = 0; i < lenSize; i++) {
		if (0==i && ')' == inputStr[i]) { //닫는괄호로 시작함.
			printf("NO\n");
			free(inputStr);
			return;
		}
		else {
			if ('(' == inputStr[i]) { //스택에 여는괄호를 넣는다 
				stack[stack_idx] = '(';
				stack_idx++;
			}
			else if (')' == inputStr[i]) { // 닫는괄호 발견.
				if (0 < stack_idx) { // 스택에 여는괄호가 있다면, 하나 삭제.
					stack[stack_idx] = 0;
					stack_idx--;
				}
				else {
					// 여는 괄호 보다, 닫힌 괄호가 더 많음. 불완전.
					printf("NO\n");
					free(inputStr);

					return;
				}
			}
		}

	}

	//printf("stack_idx : %d", &stack_idx);

	if (0 == stack_idx) {
		printf("YES\n");

	}
	else {
		printf("NO\n");
	}

	free(inputStr);
	return;

}

int main() {

	// 반복 횟수 입력 받기
	int repeat = 0;

	scanf("%d", &repeat);

	while (repeat) {
		check();
		repeat--;
	}

	return 0;
}