#include <stdio.h>
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, i, j, num, res, sum;
scanf("%d", &n);
for(i=0; i<n; i++){
sum = 0;
scanf("%d", &num);
scanf("%d", &res);
for(j=1; j<=num; j++){
sum += j;
}
if(res == sum) printf("%s\n", "YES");
else printf("%s\n", "NO");
}
return 0;
}
결과는 통과하였다.
사이트의 답안
#include<stdio.h>
int main(){
freopen("input.txt", "rt", stdin);
int n, sum=0, i, j, m, ans;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d %d", &m, &ans);
sum=0;
for(j=1; j<=m; j++){
sum+=j;
}
if(ans==sum) printf("YES\n");
else printf("NO\n");
}
return 0;
}
사이트의 답도 똑같았다.
조금 더 정리
뭔가 이대로 넘어가기엔 찜찜해서 좀 더 알아보았다. 어떤 블로그를 보니 시간복잡도 면에서 효과적인 방법을 찾았다. 원리는 다음과 같다. 10을 예로 들면 첫자리와 끝자리를 좁혀나가면서 더하면 11이 5번 나오는 것을 확인할 수 있다. 홀수인 11인 경우도 짝수 공식에 나머지 하나를 더해주면 된다.
#include <stdio.h>
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, i, j, num, res, sum;
scanf("%d", &n);
for(i=0; i<n; i++){
sum = 0;
scanf("%d", &num);
scanf("%d", &res);
if(num%2==0) sum = (1+num) * (num/2);
else sum = (1+num) * (num/2) + (num/2 + 1);
if(res == sum) printf("%s\n", "YES");
else printf("%s\n", "NO");
}
return 0;
}
두 문자열에 해당하는 알파벳의 개수만 확인하면 되므로 하나의 배열에서 첫 번째 문자열은 +로 두 번째 문자열은 -로 0이 되지 않은 인덱스가 있으면 NO, 없으면 YES로 해결하려고 했었는데 순서가 문제였다. 그래서 방법을 바꾸어 생각해 정렬을 생각해보았다. 하지만, 정렬이 어떤식으로 나오는지 몰랐기 때문에 출력을 해봤더니 대문자가 먼저 나왔다. 예) AACabee
이 점을 이용해서 순서대로 비교를해서 하나라도 다르면 NO, 모두 일치하면 YES를 출력하였다.
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
char a[100];
char b[100];
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int i;
bool flag = true;
scanf("%s", &a);
scanf("%s", &b);
sort(a, a + strlen(a));
sort(b, b + strlen(b));
for(i=0; i<strlen(a); i++){
if(a[i] != b[i]) {
flag = false;
break;
}
}
if(flag) printf("%s\n", "YES");
else printf("%s\n", "NO");
return 0;
}
여기서는 아스키 코드를 적극적으로 활용하였다. A~Z 까지는 65번~90번이고 a~z 까지는 97번~121번인 것을 말이다. (이제와서 생각해보니 맨 위 코드에서 정렬을 할 때 왜 대문자부터 나왔는지 이제 이해가 간다.) 그래서 대문자는 64를 빼고 소문자는 70을 빼서 1부터 52까지의 인덱스를 활용한 것이다.
프로그래밍을 하다보면 동적으로 메모리를 할당해 배열을 생성해야하는 경우가 발생한다. C에서는 그 역할을 malloc 함수가 한다. 이 함수는 memory allocation의 약자이며 <stdlib.h> 라이브러리에 정의되어 있기 때문에 먼저, 선언하는 작업이 필요하다.
또한, 이 함수는 인자로 전달된 크기의 바이트 수 만큼 메모리 공간을 할당한다. 입력한 n개인int형 배열을 만들기 위해서는 int 의 크기 * n이 된다. 이 때,int타입의 크기를 정확하게 알기 위해서sizeof키워드를 사용한다.
주의할 점이 있는데 이 함수는 자신이 할당한 메모리의 시작 주소를 리턴한다. 이 때, 리턴형이(void *)형이므로 (int *)형으로 형변환 하는 작업을 해야한다.
그리고 초기화 하는 방법으로 순회(for)를 돌아 값을 넣어주거나 <string.h> 라이브러리의 memset 함수를 사용한다. 이 함수는 어떤 메모리의 시작점부터 연속된 범위를 특정 값으로 지정하고 싶을 때 사용하는 함수이다. 첫 번째 인자로는 메모리의 시작점, 두 번째 인자로는 채우고자 하는 특정 값, 세 번째로는 채우고자 하는 메모리의 크기(바이트 수)가 들어간다.
1. C에서의 동적배열
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n;
scanf("%d", &n);
int *arr = (int *)malloc(sizeof(int) * n);
memset(arr, 0, n * sizeof(int));
free(arr);
동적인 배열을 다 사용하면 메모리를 다시 돌려주어야 하는데 이것은 free 함수가 한다. 이 함수는 메모리 누수를 방지하는 역할을 한다.
2. C++
C에서는 malloc과 free 함수를 통해서 메모리를 할당하고 해제하였는데 C++에서는 new와 delete라는 연산자를 활용하여 메모리를 관리한다. new는 malloc() 함수와 달리 메모리 크기를 정하지 않고 동적으로 할당한다.
2. C++에서의 동적배열
#include <iostream>
int n;
cin >> n;
int *arr = new int[n];
delete[] arr;
마땅한 방법이 떠오르지 않아 일반적인 순회(for)를 두 번 돌아 모든 경우의 수를 다 접근하며 소수를 판별하는 식으로 작성하였다.
#include <stdio.h>
using namespace std;
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, i, j, cnt = 0;
bool flag;
scanf("%d", &n);
for(i=2; i<=n; i++){
flag = true;
for(j=2; j<i; j++){
if(i%j==0){
flag = false;
break;
}
}
if(flag==true) cnt++;
}
printf("%d", cnt);
return 0;
}
결과는 예상대로 시간초과가 났다.
곰곰히 생각해봤지만 마땅한 답이 떠오르지 않아서 강의 도입부를 참조했다. 시간 초과가 나는 이유의 대부분은 굳이 참조하지 않아도 될 경우의 수를 모두 접근했을 때 발생한다는 얘기를 들었다. 소수 판별에서도 소수라고 판단이 되는 경우의 수를 제곱근으로 줄일 수 있다. 밑에 예시처럼 36을 보면 나머지가 0이되는 경우의 수는 총 10개이지만 5개만 확인해도 소수판별이 가능하다는 이야기이다.
사이트의 답안
#include <stdio.h>
using namespace std;
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, i, j, cnt = 0;
bool flag;
scanf("%d", &n);
for(i=2; i<=n; i++){
flag = true;
for(j=2; j*j<=i; j++){
if(i%j==0){
flag = false;
break;
}
}
if(flag==true) cnt++;
}
printf("%d", cnt);
return 0;
}
12번째 줄 순회(for)문에서 제곱근(sqrt 함수) 대신 왼쪽에 j를 한번 더 곱해주었다. 그 결과 통과를 했다.
조금 더 정리
소수 판별에 대해 좀 더 공부하고 싶어서 인터넷을 찾아보았다. 찾아보니에라토스테네스의 체 라는 방법이 나왔다. 논리는 다음과 같다. 2부터 입력받은 수까지 for문을 돌며 각 소수의 배수들은 소수가 아니므로 다 제외시키는 방법이다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, i, j, cnt=0;
scanf("%d", &n);
int *arr = (int *)malloc(sizeof(int) * n);
memset(arr, 0, n * sizeof(int));
for(i=2; i<=n; i++){
if(arr[i]==1) continue;
for(j = i+i; j<=n; j+=i) arr[j] = 1;
}
for(i=2; i<=n; i++){
if(arr[i]!=1) cnt++;
}
printf("%d", cnt);
free(arr);
return 0;
}
입력받은 수를 뒤집는 함수인 reverse 함수는 순회(while)를 돌면서 res 변수에 10씩 곱해주고 나머지를 더해주면 되었고 소수를 판별하는 isPrime 함수는 2부터 자기자신 전까지의 숫자를 순회(for)를 돌면서 나머지가 0이되는 숫자가 있으면 소수가 아니라고 판단하였다.
#include <stdio.h>
using namespace std;
int reverse(int x){
int num, res = 0;
while(x>0){
num = x%10;
res = res * 10 + num;
x /= 10;
}
return res;
}
bool isPrime(int x){
bool flag = true;
for(int i=2; i<x; i++){
if(x%i==0) {
flag = false;
break;
}
}
return flag;
}
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, i, a, rev;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &a);
rev = reverse(a);
if(isPrime(rev)){
printf("%d\n", rev);
}
}
return 0;
}
그 결과 틀린 케이스가 2개가 발견되었다.
알고보니 10과 100의 뒤집은 숫자 1은 소수가 아니기 때문에 따로 1은 소수가 아니라는 작업을 해줬어야 했다. 조건문으로 따로 빼서 코드를 추가하였다.
#include <stdio.h>
using namespace std;
int reverse(int x){
int num, res = 0;
while(x>0){
num = x%10;
res = res * 10 + num;
x /= 10;
}
return res;
}
bool isPrime(int x){
bool flag = true;
if(x==1) flag = false;
for(int i=2; i<x; i++){
if(x%i==0) {
flag = false;
break;
}
}
return flag;
}
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, i, a, rev;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &a);
rev = reverse(a);
if(isPrime(rev)){
printf("%d\n", rev);
}
}
return 0;
}
그 결과 통과를 했다.
사이트의 답안
#include<stdio.h>
int reverse(int x){
int res=0, tmp;
while(x>0){
tmp=x%10;
res=res*10+tmp;
x=x/10;
}
return res;
}
bool isPrime(int x){
int i;
if(x==1) return false;
bool flag=true;
for(i=2; i<x; i++){
if(x%i==0){
flag=false;
break;
}
}
return flag;
}
int main(){
freopen("input.txt", "rt", stdin);
int n, num, i, tmp;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d", &num);
tmp=reverse(num);
if(isPrime(tmp)) printf("%d ", tmp);
}
return 0;
}
문제를 보자마자 배열의 0~9 index를 이용해 값을 저장하고 최대값을 찾으려고 하였다. 주어진 입력 조건에 자연수의 길이는 100을 넘지 않는다고 되어 있는데 최대가 99이므로 long long 타입으로도 받을 수 없었다. char형 배열을 이용해서 각각을 정수로 바꿔주는 방법을 시도하였다.
#include <stdio.h>
using namespace std;
char array[101];
int digit[11];
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int i, temp, max, index;
scanf("%s", &array);
for(i=0; array[i]!='\0'; i++){
temp = array[i] - '0';
digit[temp]++;
}
for(i=0; i<10; i++){
if(digit[i]>=max) {
max = digit[i];
index = i;
}
}
printf("%d", index);
return 0;
}
그 결과 통과를 했다.
사이트의 답안
#include<stdio.h>
int ch[10];
int main(){
//freopen("input.txt", "rt", stdin);
int i, digit, max=-2147000000, res;
char a[101];
scanf("%s", &a);
for(i=0; a[i]!='\0'; i++){
digit=a[i]-48;
ch[digit]++;
}
for(i=0; i<=9; i++){
if(ch[i]>=max){
max=ch[i];
res=i;
}
}
printf("%d\n", res);
return 0;
}
#include <stdio.h>
using namespace std;
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, cnt, i, temp;
scanf("%d", &n);
for(i=1; i<=n; i++){
temp = i;
while(temp>0){
temp /= 10;
cnt++;
}
}
printf("%d", cnt);
return 0;
}
결과는 범위가 10억까지 늘어서 그런지 Time Limit이 걸려서 통과하지 못했다.
그래서 방법을 바꾸어 생각해보았다. 위에서 작성한 분기문을 순회(while)문을 사용해서 작성하였다. 각각의 자릿수에 해당하는 수의 개수는 9(1~9), 90(10~99), 900(100~999), 9000(1000~9999) .... 규칙적으로 10이 곱해져서 증가하는 것을 이용하였다.
입력받은 n의 자리수를 확인하기 위한 check 변수와 각 자리수의 숫자 개수를 확인하기 위해 임시로 사용한 temp 변수와 각 자리수를 나타내는 digit 변수를 사용해서 코드를 완성했다.
문제를 봤을 때 자릿수를 기준으로 count값을 증가시키면 된다는게 핵심이라고 생각했고 이 자릿수를 어떻게 구별할지에 대해 곰곰히 생각해보았다. 처음 든 생각은 입력된 n까지 순회(for)를 돌면서 그 안에서 또 while문을 돌아 10으로 나누어 count값을 증가시키는 쪽으로 생각을 했다.
그러다 문제를 더 읽다보니 입력 설명에서 조건이 십만 미만이라고 한 점에서 분기문만 이용해서 처리해도 된다고 생각을 했다. 15인 두 자리수를 예로 들면 한 자리수는 1만 증가시켜주면 되므로 총합은 9이다. 따라서 15에서 9를 뺀 나머지 6에 2를 곱해주면 된다고 생각했고 100인 세 자리수를 예로 들면 한 자리수에 해당하는 9와 십의 자리수에 해당하는 10~99까지 총 90개를 곱하기 2해주고 나머지 세 자리수인 100만 3을 더해주면 된다고 생각했다.
먼저, 각 자리수의 합을 구해주는 함수를 정의해주고 입력된 n개의 수마다 함수를 호출하였다. 문제에서 요구하는 것은 처음에 입력받은 값(아래 코드에서 num 변수)이였기 때문에 각 자리 수의 합을 비교하는 변수들(res와 max)이 필요했다. 또한, 문제에서 자리수의 합이 같은 경우 값이 가장 큰 값을 출력하라고 했기 때문에 값을 비교하는 변수들(num과 dap)이 필요했다.
#include <stdio.h>
using namespace std;
int digit_sum(int x){
int sum = 0;
while(x>=1){
sum += x%10;
x = x/10;
}
return sum;
}
int main(int argc, char** argv) {
//freopen("input.txt", "rt", stdin);
int n, num, res, max=0, dap, i;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &num);
res = digit_sum(num);
if(res >= max){
if(res == max){
max = res;
dap = (num > dap) ? num : dap;
}
else {
max = res;
dap = num;
}
}
}
printf("%d\n", dap);
return 0;
}
그 결과 통과를 했다.
사이트의 답안
#include<stdio.h>
int digit_sum(int x){
int sum=0, tmp;
while(x>0){
tmp=x%10;
sum=sum+tmp;
x=x/10;
}
return sum;
}
int main(){
freopen("input.txt", "rt", stdin);
int n, num, i, sum, max=-2147000000, res;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d", &num);
sum=digit_sum(num);
if(sum>max){
max=sum;
res=num;
}
else if(sum==max){
if(num>res) res=num;
}
}
printf("%d\n", res);
return 0;
}
