습관처럼

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW8Wj7cqbY0DFAXN&categoryId=AW8Wj7cqbY0DFAXN&categoryType=CODE

문제 설명

한빈이는 퇴근길에 스팟마트에 들러 과자 두 봉지를 사서 양 손에 하나씩 들고 가려고 한다. 

스팟마트에는 N개의 과자 봉지가 있으며, 각 과자 봉지는 ai그램의 무게를 가진다. 

배가 많이 고픈 한빈이는 최대한 양이 많은 (무게가 많이 나가는) 과자 봉지를 고르고 싶으나, 

과자 두 봉지의 무게가 M 그램을 초과하면 무거워서 과자를 들고 다닐 수 없다. 

한빈이가 들고 다닐 수 있는 과자들의 최대 무게 합을 출력하라. 한빈이는 과자를 “정확히” 두 봉지 사야 함에 유의하라.

문제 풀이 

완전 탐색으로 모든 경우의 수를 돌리면서 무개 범위에 만족되는 값 중에서 최댓값을 출력하고 없을 경우 default값인 -1을 출력한다.

코드

#include<iostream>
#include <algorithm>

using namespace std;
int testcase=0;

int main(){
    cin>>testcase;
    int n,weight;
    int a[1001];
    for(int i=1;i<=testcase;i++){
    	cin>>n>>weight;
        for(int t=0;t<n;t++) cin>>a[t];
        int ans=-1;
        for(int l=0;l<n-1;l++){
        	for(int m=l+1;m<n;m++){
                int temp=a[l]+a[m];
                if(temp<=weight) ans=max(ans,temp);
            	else continue;
            }
        }
        cout<<"#"<<i<<" "<<ans<<"\n";
       
	}
}

funny algorithms :) ~

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW4Z8x2KAL8DFAQ7&categoryId=AW4Z8x2KAL8DFAQ7&categoryType=CODE#none

문제 설명

‘a’와 ‘b’가 번갈아 나오는 길이 L인 문자열이 있다. L = 5이면 “ababa”이고, L = 7이면 “abababa”이다.

홀수 L이 주어질 때, ‘a’와 ‘b’가 번갈아 나오는 길이 L인 문자열에서, 

길이가 2이상인 연속한 부분 문자열이 회문(앞으로 읽어도 뒤로 읽어도 같은 문자열)인 것의 개수를 구하는 프로그램을 작성

문제 풀이

홀수이므로 규칙을 만들어 보면 2n+1인 홀수의 개수. 즉, 2n+1을 만족하는 n의 제곱이 답이 된다. 홀수의 합은 홀수의 개수의 제곱

코드

이번 문제풀이에서 중요한 핵심은 라이브러리에서 cmath의 pow 함수의 속도보다 기본적인 방법이 속도가 빠른 측면이 있다. 간단한 수학 계산인 경우. 따라서 시간 초과가 발생한 코드와 시간 초과가 발생하지 않은 코드 두 개가 존재합니다.

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int test_case,n;
    long long ans;
    cin>>test_case;
    for (int t=1;t<=testcase;t++)
    {
        cin>>n;
        long long temp = (n-1)/2;
        cout<<"#"<<t<<' '<<temp*temp<<'\n';
    }
    return 0;
}

시간 초과가 발생한 코드

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int test_case,n;
    long long ans;
    cin>>test_case;
    for (int t=1;t<=testcase;t++)
    {
        cin>>n;
        long long temp = (n-1)/2;
        cout<<"#"<<t<<' '<<pow(temp,2)<<'\n';
    }
    return 0;
}

funny algorithms :) ~