λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
πŸ”₯ PS(Problem Solving) πŸ”₯/BOJ

[BOJ] #12789 도킀도킀 κ°„μ‹λ“œλ¦¬λ―Έ

by dar0m! 2020. 6. 2.
μ‹œκ°„ μ œν•œ λ©”λͺ¨λ¦¬ μ œν•œ μ •λ‹΅ λΉ„μœ¨
 1초  128MB 40.486%
 

12789번: 도킀도킀 κ°„μ‹λ“œλ¦¬λ―Έ

μΈν•˜λŒ€ν•™κ΅ ν•™μƒνšŒμ—μ„œλŠ” 쀑간, 기말고사 λ•Œλ§ˆλ‹€ μ‹œν—˜ 곡뢀에 μ§€μΉœ ν•™μš°λ“€μ„ μœ„ν•΄ 간식을 λ‚˜λˆ μ£ΌλŠ” 간식 λ“œλ¦¬λ―Έ 행사λ₯Ό μ‹€μ‹œν•œλ‹€. μŠΉν™˜μ΄λŠ” μ‹œν—˜ 기간이 될 λ•Œλ§ˆλ‹€ 간식을 받을 생각에 두근두��

www.acmicpc.net

 

문제

학생듀이 μˆœμ„œλŒ€λ‘œ 쀄을 μ„œλ €κ³  ν–ˆμ§€λ§Œ 곡간이 λ„ˆλ¬΄ ν˜‘μ†Œν•΄μ„œ λ§ˆμŒλŒ€λ‘œ 이동할 수 μ—†μ—ˆλ‹€. λ‹€ν–‰νžˆλ„ λŒ€κΈ°μ—΄μ˜ μ™Όμͺ½μ—λŠ” 1μ—΄λ‘œ μ„€ 수 μžˆλŠ” 곡간이 μ‘΄μž¬ν•˜μ—¬ 이 곡간을 잘 μ΄μš©ν•˜λ©΄ λͺ¨λ‘κ°€ μˆœμ„œλŒ€λ‘œ 간식을 받을 수 μžˆμ„μ§€λ„ λͺ¨λ₯Έλ‹€. 자칫 간식을 λͺ» λ°›κ²Œ 될지도 λͺ¨λ₯Έλ‹€λŠ” μœ„κΈ°κ°μ„ λŠλ‚€ μŠΉν™˜μ΄λŠ” μžμ‹ μ˜ 컴퓨터 μ•Œκ³ λ¦¬μ¦˜μ  지식을 ν™œμš©ν•΄ κ³Όμ—° λͺ¨λ“  μ‚¬λžŒλ“€μ΄ μˆœμ„œλŒ€λ‘œ 간식을 받을 수 μžˆλŠ”μ§€ ν™•μΈν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ λ§Œλ“€κΈ°λ‘œ ν–ˆλ‹€. λ§Œμ•½ λΆˆκ°€λŠ₯ ν•˜λ‹€λ©΄ μŠΉν™˜μ΄λŠ” 이번 쀑간고사λ₯Ό 망치게 될 것 이고 κ°€λŠ₯ν•˜λ‹€λ©΄ νž˜μ„ μ–»μ–΄ 쀑간고사λ₯Ό 잘 λ³Ό 수 μžˆμ„μ§€λ„ λͺ¨λ₯Έλ‹€.

μ‚¬λžŒλ“€μ€ ν˜„μž¬ 1μ—΄λ‘œ 쀄을 μ„œμžˆκ³ , 맨 μ•žμ˜ μ‚¬λžŒλ§Œ 이동이 κ°€λŠ₯ν•˜λ‹€. μΈκ·œλŠ” λ²ˆν˜Έν‘œ μˆœμ„œλŒ€λ‘œλ§Œ 톡과할 수 μžˆλŠ” 라인을 λ§Œλ“€μ–΄ λ‘μ—ˆλ‹€. 이 라인과 λŒ€κΈ°μ—΄μ˜ 맨 μ•ž μ‚¬λžŒ μ‚¬μ΄μ—λŠ” ν•œ μ‚¬λžŒμ”© 1열이 λ“€μ–΄κ°ˆ 수 μžˆλŠ” 곡간이 μžˆλ‹€. ν˜„μž¬ λŒ€κΈ°μ—΄μ˜ μ‚¬λžŒλ“€μ€ 이 κ³΅κ°„μœΌλ‘œ 올 수 μžˆμ§€λ§Œ λ°˜λŒ€λŠ” λΆˆκ°€λŠ₯ν•˜λ‹€. μŠΉν™˜μ΄λ₯Ό 도와 ν”„λ‘œκ·Έλž¨μ„ μ™„μ„±ν•˜λΌ.

μž…μΆœλ ₯

μž…λ ₯의 첫째 μ€„μ—λŠ” ν˜„μž¬ μŠΉν™˜μ΄μ˜ μ•žμ— μ„œ μžˆλŠ” ν•™μƒλ“€μ˜ 수 N(1 ≤ N ≤ 1,000,μžμ—°μˆ˜)이 주어진닀.
λ‹€μŒ μ€„μ—λŠ” μŠΉν™˜μ΄ μ•žμ— μ„œμžˆλŠ” λͺ¨λ“  ν•™μƒλ“€μ˜ λ²ˆν˜Έν‘œ(1,2,...,N) μˆœμ„œκ°€ μ•žμ—μ„œλΆ€ν„° λ’€ μˆœμ„œλ‘œ 주어진닀.

μŠΉν™˜μ΄κ°€ λ¬΄μ‚¬νžˆ 간식을 받을 수 있으면 "Nice"(λ”°μ˜΄ν‘œλŠ” μ œμ™Έ)λ₯Ό 좜λ ₯ν•˜κ³  그렇지 μ•Šλ‹€λ©΄ "Sad"(λ”°μ˜΄ν‘œλŠ” μ œμ™Έ)λ₯Ό 좜λ ₯ν•œλ‹€.

 

ν•΄κ²°

key point, N의 크기가 μž‘μœΌλ―€λ‘œ 이쀑 forλ¬Έ ν™œμš©
  • st λ³€μˆ˜λŠ” λ‹€μŒμœΌλ‘œ κ°„식을 λ°›μ•„μ•Όν•˜λŠ” ν•™μƒμ˜ λ²ˆν˜Έμ΄λ‹€.
  • st 와 ν˜„μž¬ ν•™μƒμ˜ λ²ˆν˜Έκ°€ μΌμΉ˜ν•΄μ•Όλ§Œ 간식을 받을 수 μžˆλ‹€.
  • λ§Œμ•½ λ‹€λ₯΄λ‹€λ©΄, stack이 λΉ„μ–΄μžˆλŠ”μ§€ ν™•μΈν•œλ‹€.
    • λΉ„μ–΄μžˆμ§€ μ•Šλ‹€λ©΄ μŠ€νƒ λ¨Όμ € νƒμƒ‰ν•œλ‹€.
    • 탐색이 λλ‚˜κ±°λ‚˜, μ• μ΄ˆμ— λΉ„μ–΄μžˆμ—ˆλ‹€λ©΄ stack에 μŒ“λŠ”λ‹€.
  • n번 λ™μ•ˆ λ°˜λ³΅ν–ˆλŠ”λ°(반볡문 μ’…λ£Œ ν›„)
    • stack이 λΉ„μ–΄μžˆλ‹€λ©΄ λͺ¨λ“  학생이 간식을 받은 κ²ƒμœΌλ‘œ Niceλ₯Ό 좜λ ₯
    • stack에 학생듀이 λ‚¨μ•„μžˆλ‹€λ©΄, topμœ„μΉ˜μ— μžˆλŠ” 학생이 간식을 λ°›μ•„μ•Όν•˜λŠ” ν•™μƒμ˜ λ³€ν˜Έ(st)와 μΌμΉ˜ν•˜λŠ”μ§€ ν™•μΈν•œλ‹€.
      • ν•œ λ²ˆμ΄λΌλ„ μΌμΉ˜ν•˜μ§€ μ•Šμ•˜λ‹€λ©΄, Sadλ₯Ό 좜λ ₯ν•˜κ³  μ’…λ£Œν•œλ‹€.
      • while문을 μ •μƒμ μœΌλ‘œ λλƒˆλ‹€λ©΄ Niceλ₯Ό 좜λ ₯ν•œλ‹€. 

 

μ½”λ“œ

λ©”λͺ¨λ¦¬ μ‹œκ°„
 2024 KB  0 ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
 
int n, num;
int stack[10005], top, st = 1;
 
int main() {
    scanf("%d"&n);
 
    while (n--) {
        scanf("%d"&num);
        if (st == num) {
            st++;
        }
        else {
            while (top > 0 && stack[top - 1== st) {
                top--; st++;
            }            
            stack[top++= num;            
        }
    }
    while (top >= 1) {
        if (st == stack[top - 1]) {
            st++; top--;
        }
        else {
            printf("Sad"); return 0;
        }
    }
    printf("Nice");
 
    return 0;
}
cs

 

'πŸ”₯ PS(Problem Solving) πŸ”₯ > BOJ' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

[BOJ] #5670 νœ΄λŒ€ν° 자판  (0) 2020.06.12
[BOJ] #5052 μ „ν™”λ²ˆν˜Έ λͺ©λ‘  (0) 2020.06.08
[BOJ] #1406 에디터  (0) 2020.06.02
[BOJ] #2164 μΉ΄λ“œ2  (0) 2020.06.02
[BOJ] #14830 κ²½μ‚¬λ‘œ  (0) 2020.05.21

λŒ“κΈ€