[알고리즘] 백준알고리즘 10824번 네 수

안녕하세요 감자 코딩 & 감자 개발자입니다. 이번에 살펴볼 문제는 10824번의 문제인 "네 수" 라는 문제입니다.

가장 큰 핵심 키워드는 자료형 변수의 범위에 따라 문제를 해결 할 수 있냐입니다.

---

문제 링크

https://www.acmicpc.net/problem/10824

네 수 성공

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초 256 MB 8240 3042 2548 37.295%

문제

네 자연수 A, B, C, D가 주어진다. 이때, A와 B를 붙인 수와 C와 D를 붙인 수의 합을 구하는 프로그램을 작성하시오.

두 수 A와 B를 합치는 것은 A의 뒤에 B를 붙이는 것을 의미한다. 즉, 20과 30을 붙이면 2030이 된다.

입력

첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000)

출력

A와 B를 붙인 수와 C와 D를 붙인 수의 합을 출력한다.

예제 입력 1 

10 20 30 40

예제 출력 1 

4060

---

문제를 차근차근 읽어봅시다

문제 해결 방식

1) 자연수 a,b,c,d가 주어지고 a와 b를 붙이고 c와 d를 붙인후 ab합친 값과 cd합친값을 더하라는 문제입니다.

2) 뭐그렇게 별로 어렵지 않아보이는 문제 같아 보입니다.

하지만! 간과해서는 안될 조건이 하나 있습니다.

첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000)

라는 조건입니다. 이게 왜? 뭐가 잘못된거지? 그냥 4개 수다 1,000,000까지 할 수 있다 라는말아닌가? 라고 생각할 수 있습니다. 하지만 정말 큰 오산입니다. 일단 C언어에서 사용하는 자료형들의 메모리크기위 값의 범위를 확인해봅시다.

<C언어 자료형 정리> 

자료형	키워드	메모리 크기	값의 범위
문자형	char	1 Bytes	-128~127
정수형	short	2 Bytes	-32,768~32,767
	int	4 Bytes	-2,147,483,648 ~ 2,147,438,647
	long	4 Bytes	-2,147,483,648  ~2.147.483.647
부호없는 문자형	unsigned char	1 Bytes	0~255
부호없는 정수형	unsigned short	2 Bytes	0~65,535
	unsigned int	4 Bytes	0~4,294,967,295
	unsigned long	4 Bytes	0~4,294,967,295
부동 소수형	float	4 Bytes	1.2E-38~3.4E38
	double	8 Bytes	2.2E-308~1.8E308
void형	void	0 Bytes	값 없음

3) 어떠신가요? 뭔가 범위가 잘못되었다고 느끼셨나요? 못느끼셨을분들이 대부분일 수도 있습니다. 왜냐하면 범위계산을 해보신분들은 많이 없을거라고 생각이 듭니다.

일단 차근차근 하나씩 뜯어봅시다.

a,b,c,d 변수 선언 여기서 중요한것 ! 문제에서 1,000,000 까지의 수를 입력이 가능하다고 하였습니다. 

최대 입력범위를 생각하였을때 a(1,000,000),b(1,000,000) +c(1,000,000),d(1,000,000) 이므로 최대 4,000,000,000,000까지의 범위를 갖습니다. 이해하셨나요? 

기존의 int범위를 생각했을때 약 21억 정도이므로, int자료형으로 값을 저장해서 출력해버리면 오버플로우가 발생하므로 long long 자료형을 써야겠다고 생각을 했습니다. C++11부터 생겨난 자료형이라고 하네요. 

저도 이것때문에 잠깐 삽질을 하였지만, 다행히도 금방 알아내어서 풀수있었습니다.

4) 그러면 저희는 a,b의 값을 합치고 c,d값을 합칠것입니다. 이때 가장 잘 사용하는 함수는 to_string함수를 사용할것입니다. integer -> string으로 변환시켜주는 함수입니다. string으로 바꿔준후 a,b / c,d값을 뒤에 이어붙여주어야겠지요? 

그러면 또 무엇이 필요할까요? 문자들을 다시 long long타입형태로 바꾸어 주어야지 이값들을 최종 결과값을 뽑아낼 수 있습니다. 이때 사용하는 함수는

stoll함수를 사용할것입니다. 이 함수는 string -> long long 타입으로 변환시켜줍니다.그외 나머지함수에 대해 살펴보죠.

strtol : 문자열을 long 값으로 변환 합니다. 2진수, 8진수, 16진수 값을 10진수로 변환 합니다. (string to long)

strtoul : 문자열을 unsigned long 값으로 변환 합니다. (string to unsigned long)

strtod : 문자열을 double 값으로 변환 합니다. (string to double)

이외에도 많은 함수들이 있지만, 나중에 시간을 내서 따로 정리를 해보도록 하겠습니다.

코드 리뷰

//

//  10824(네수).cpp

//  beakjoon_algorithm

//

//  Created by kgh on 22/12/2018.

//  Copyright © 2018 kgh. All rights reserved.

//

#include <stdio.h>

#include <stdlib.h>

#include <string>

#include <iostream>

using namespace std;

int main(void){

    

    // a,b,c,d 변수 선언 여기서 중요한것 ! 문제에서 1,000,000 까지의 수를 입력이 가능하다고 하였다.

    // 최대 입력범위를 생각하였을때 a(1,000,000),b(1,000,000) + c(1,000,000),d(1,000,000) 이므로 최대 4,000,000,000,000까지의 범위를 갖는다. 기존의 int범위를 생각했을때 약 21억 정도이므로, int자료형으로 값을 저장해서 출력해버리면 오버플로우가 발생하므로 long long 자료형을 써야겠다고 생각을 함.

    

    int a,b,c,d =0;

    string result1, result2;

    // 값 입력

    scanf("%d %d %d %d",&a,&b,&c,&d);

    

    // integer to String 변환

    result1 = to_string(a) + to_string(b);

    result2 = to_string(c) + to_string(d);

    

    // long long은 8바이트의 공간을 가지는 자료형이기에 signed long long을 기준으로 하면 최대 계산할 수 있는 양의 정수 범위는 0 ~ 9,223,372,036,854,775,807(16진수로 7FFFFFFFFFFFFFFF)가 되어 범위가 큰 문제를 해결 할 수 있게되었다.

    long long A = stoll(result1);

    long long B = stoll(result2);

    cout << A + B << endl;

    return 0;

}

어떠신가요? 이번기회에 자료형 관련된 범위문제도 한번더 생각해볼 수 있던 문제였던것 같습니다.

아직 생소하신분들도 있을텐데, 알고리즘에 대한 센스를 늘려가기 위해서는 이런것들이 바탕이 되어야된다고 생각을 합니다.

이상 감자코딩 & 감자개발자였습니다. 감사합니다 :)