괄호를 잃어버려서 퇴사할래!(백준 1541,14501)

 

반갑습니다. 백준 문제 푼거 관련해서 처음으로 글을 쓰네요. 제 실력을 키우기 위해 간간히 기억에 남는 문제들을 쓰겠습니다. 남의 코드를 살짝 참고해서 기억에 안 남을까봐 블로그에까지 쓰는 건 절대 맞습니다.

---

오늘 다룰 두 문제는 14501 퇴사 문제와 1541 잃어버린 괄호 문제입니다.일단 먼저 푼 14501번 퇴사 문제부터 다뤄 볼게요.

대표사진 삭제

사진 설명을 입력하세요.

이 문제는 삼성전자 SW 역량 테스트 기출 문제더라고요? 그래서 그런지 문제가 좋더라고요. 저는 처음에는 엄청 쉽다고 생각해서 삼전 그냥 들어가겠네 생각했는데 역시 쉬울 리가 없었어요.

문제 설명을 간단히 하자면 어떻게 해야 퇴사 전에 가장 많은 돈을 챙길수 있냐는 거였어요.

#include<stdio.h>
typedef struct {
    int T;
    int P;
}file;
//구조체 선언
int main (void)
{
    file list[17];
    int N,Max=0;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%d %d",&list[i].T,&list[i].P);
    }
    for(int i=1;i<=N;i++)
    {
        int sum=0;
        for(int j=i;j<=N;j++)
        {
            if(j-i<list[i].T&&j!=i)
                continue;
            if(j+list[j].T>N+1)
                continue;
            sum+=list[j].P;
        }
        if(Max<sum)
            Max=sum;
    }
    printf("%d",Max);
}

 

대표사진 삭제

사진 설명을 입력하세요.

이 코드는 처음부터 더해가는 거였어요. 그러자 4번째 테스트 케이스에서 문제가 생기더라고요. 제 코드에서는 7일차에서 20을 택하면 8일차에서 30을 택하지 못해요. 그래서 뒤에서 부터 하자라는 생각이 들었죠. 이것 말고도 왜 다이나믹 프로그래밍이 태그에 있는데 안 쓰고 있을까라는 생각이 들어서 다이내믹 프로그래밍을 이용해서 했을 때와 안 했을때를 구분해보자라고 생각을 했어요. 그걸 구현한게 이제 다음 코드에요.

#include<stdio.h>
typedef struct{
    int T;
    int P;
}file;
int Max(int a,int b)
{
    return  a>b ? a : b;
}
int main (void)
{
    int N,dp[17]={0,};
    file list[17];
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%d %d",&list[i].T,&list[i].P);
    }
    for(int i=N;i>=0;i--)
    {
        if(i+list[i].T>N+1)
        {
            dp[i]=0;
            dp[i]=Max(dp[i+1],0);
        }
        else
            dp[i]=Max(dp[i+1],dp[i+list[i].T]+list[i].P);
    }
    printf("%d",dp[1]);
}

 

도움이 되었나요? 다음 문제는 이제 괄호 잃어버린 문제에요. 근데 갑자기 의문이 들었어요. 이거 쓴다고 늘까요? 모르겟어요 그래도 마무리는 할게요.

 

이건 temp를 활용하는 방식이 신기햇어요. 이정도로만 할게요. - 뒤에를 모두 더한다는 생각은 하기 쉬웠는데, 그걸 구현하기가 생각보다 번거롭고 빡센 문제였어요.

#include<stdio.h>
#include<string.h>
int main(void)
{
    char str[51];
    scanf("%s",str);
    int len=(int)strlen(str),temp=0,sum=0;
    for(int i=0;i<=len;i++)
    {
        if(str[i]=='-'||i==len)
        {
            sum+=temp;
            temp=0;
            for(int j=i+1;j<=len;j++)
            {
                if(j==len)
                {
                    sum-=temp;
                    goto end;
                }
                else if(str[j]=='+'||str[j]=='-')
                {
                    sum-=temp;
                    temp=0;
                }
                else
                {
                    temp*=10;
                    temp+=str[j]-'0';
                }
               
            }
        }
        else if(str[i]=='+')
        {
            sum+=temp;
            temp=0;
        }
        else
        {
            temp*=10;
            temp+=str[i]-'0';
        }
        
    }
end:
    printf("%d\n",sum);
}

 

이상 나중에 다시 생각나면 보려고 쓴 블로그 글이었어요. 다들 즐거운 시간 되세용 뿅!