Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 시뮬레이션
- 해커랭크
- C++
- koitp
- 소수
- 백준
- 삼성 SDS 대학생 알고리즘 특강
- 다이나믹 프로그래밍
- sw expert academy
- 에라토스테네스의 체
- dfs
- dynamic programming
- 삼성 기출
- 동적 계획법
- hackerrank
- 완전탐색
- 맛집
- 백트래킹
- BOJ
- Algorithm
- DP
- 스택
- 그리디
- 브루트포스
- 잠실
- 알고리즘
- SWEA
- 구현
- PS
- BFS
Archives
- Today
- Total
펭로그
[C++] 백준 BOJ 10799 쇠막대기 본문
문제링크 : https://www.acmicpc.net/problem/10799
( 은 쇠막대기의 시작점이고 ) 은 쇠막대기의 끝나는 부분이고 ( ) 은 레이저를 나타낸다.
두 괄호 사이(쇠막대기)에는 반드시 ( ) 이 올 수밖에 없다.
1. 열린 괄호의 갯수는 닫힌 괄호의 갯수와 동일해야 한다.
2. 열린 괄호가 증가하다가 감소하는 시점 ( ) 은 반드시 레이저이다.
3. 레이저 ( )를 제외하고 레이저의 좌측 부분에 열린 괄호가 몇개인지를 세면 레이저를 기준으로 좌측의 잘린 쇠막대기의 판이 몇개인지 알 수 있다. 열린 괄호를 읽을 때 마다 카운트를 세면 될 것이다.
4. 레이저 ( ) 우측 편부터 닫힌 괄호 ) 가 오면 쇠막대기 카운트를 하나씩 감소시킨다.
여기서 찾을 수 있는 규칙은 ( 의 경우 반드시 다시 ) 를 만나야 하기 때문에 ( ) 를 만나기 이전 까지의 쇠막대기를 카운트 하면 된다.
그리고 이 쇠막대기들은 반드시 ( )에 의해서 분리된다. 분리될 시점의 카운트 값을 결과 값에 저장하면 된다.
그리고 )의 경우는 다음에 만나는 ( )에 의해서 분리되지 않는 것을 확인할 수 있다. 그냥 쇠막대기의 갯수가 감소할 때마다 하나씩 결과 값에 바로 저장하면 된다.
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 | // BOJ 10799 쇠막대기 #include <bits/stdc++.h> using namespace std; int main() { //freopen("../input.txt", "r", stdin); char input; char old; int result = 0; int cnt = 0; for (int n = 0; cin >> input; n++) { if (input == '(') cnt++; else { cnt--; if (old == '(') result += cnt; else result++; } old = input; } cout << result; return 0; } | cs |
'Study > PS(Algorithm)' 카테고리의 다른 글
[C++] 삼성 SDS KOITP 큰수만들기 (0) | 2018.07.22 |
---|---|
[C++] 삼성 SDS KOITP 보물찾기 (0) | 2018.07.21 |
[C++] 삼성 SDS KOITP 전화상담 (3) | 2018.07.20 |
[C++] 삼성 SDS KOITP 고장난시계 (0) | 2018.07.19 |
[C++] 삼성 SDS KOITP 마지막생존자 (0) | 2018.07.19 |
Comments