백준 17952 C언어

어제부터 쭉 고민했던 문제인데 드디어 풀었다..!

많은 시도 끝에 풀었다..

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

17952번: 과제는 끝나지 않아!

 

문제

성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이다. 다행히 과제 제출 기한은 학기가 끝날 때까지이다. 너무나도 많은 과제를 하다가 미쳐버린 성애는 아래와 같은 규칙으로 과제를 해 나가고 있다.

1. 과제는 가장 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다.
2. 과제를 하던 도중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행한다.
3. 새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다. (성애는 기억력이 좋기 때문에 아무리 긴 시간이 지나도 본인이 하던 부분을 기억할 수 있다.)

성애는 과제를 받자마자 이 과제가 몇 분이 걸릴지 정확하게 알 수 있고, 성애가 제출한 과제는 무조건 만점을 받는다.

성애는 이번 학기에 자기가 받을 과제 점수를 예상해보고 싶다. 하지만 과제 점수를 예상하는 지금도 과제가 추가되고 있기에 여유를 부릴 수가 없다. 여러분이 성애가 받을 과제 점수를 구해주자!

---

입력

첫째 줄에 이번 학기가 몇 분인지를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

두번째 줄부터 N줄 동안은 학기가 시작하고 N분째에 주어진 과제의 정보가 아래의 두 경우 중 하나로 주어진다.

• 1 A T: 과제의 만점은 A점이고, 성애가 이 과제를 해결하는데 T분이 걸린다. A와 T는 모두 정수이다. (1 ≤ A ≤ 100, 1 ≤ T ≤ 1,000,000)
• 0: 해당 시점에는 과제가 주어지지 않았다.

  ---

  출력
• 성애가 받을 과제 점수를 출력한다.

  ---

해결방안->처음에 스택을 이용해서 풀다가 안풀리고 뭔가 굉장히 꼬인거같아서 연결리스트를 활용한 스택으로 풀었다.

처음에 연결리스트에서의 노드 구조체에서 시간과 점수의 값을 가진 상태로 정의한다.

n번 동안 반복문을 돌리면서 값을 입력받는다.

값이 0이아니면 Push연산을 하고 값이 0이면 Pop연산을 한다. 

이떄 Push연산이나 Pop연산을 할때 시간이 0이 나오면 값을 더해주고 그 노드를 삭제시킨다.(문제를 풀었으니깐)

 

전체소스 코드->

#include <stdio.h>

#include <stdlib.h>

#define True 1

#define False 0

 

int sum = 0;

 

typedef struct _node{ //노드의 구조체(점수값과 시간값)

    int data;

    int time;

    struct _node *next;

}Node;

 

typedef struct _listStack{

    Node *head;

}ListStack;

 

typedef ListStack Stack;

 

void Stackinit(Stack *pstack){

    pstack->head = NULL;

}

 

int Empty(Stack *pstack){

    if(pstack->head == NULL)

        return True;

    else

        return False;

}

 

void Push(Stack *pstack,int data,int time){ //push연산

    Node *newnode = (Node*)malloc(sizeof(Node)); 

    newnode->data = data;

    newnode->time = time - 1; //노드에 점수를 넣고 시간값을 넣어준다

    newnode->next = pstack->head; 

    pstack->head = newnode;

    if(newnode->time == 0){ //시간값이 0이라면 점수를 더해주고 그 노드를 free시킨다

         Node *delnode = pstack->head;

        sum = sum + delnode->data;

        pstack->head = pstack->head->next;

        free(delnode);

    }

}

 

void Pop(Stack *pstack){ //pop연산

    if(Empty(&pstack)){

        exit(0);

    }

      pstack->head->time = pstack->head->time - 1; //시간값을 1 줄인다

 

        if(pstack->head->time == 0){ //마찬가지로 시간값이 0이라면 점수를 더하고 노드를 Free시킨다

        Node *delnode = pstack->head;

        sum = sum + delnode->data;

        pstack->head = pstack->head->next;

        free(delnode);

    }

 

 

}

 

 

int main(void){

    Stack stack;

    Stackinit(&stack); //스택 생성과 초기화

    int n;

    scanf("%d",&n);

    for(int i = 0;i<n;i++){

        int x; 

        scanf("%d",&x);

        if(x != 0){ //x가 0이아닐때 시간,점수 입력받기

           int a;

            int t;

            scanf("%d %d",&a,&t);

            Push(&stack,a,t); //Push연산(x!=0)

        }

        else if(x == 0 && !Empty(&stack)) { //Pop연산

            Pop(&stack);

        }

    }

    printf("%d",sum);

}