반응형

백준 큐 4

백준 3190 뱀 c++ [컴공과고씨]

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 해결 방법은 2차원 배열을 이용해서 map을 만들어주고 사과가 있는 칸에는 1을 넣어준다. 입력으로 시간과 방향 정보를 받아 준다. 방향을 바꾸기 전까지 반복문을 돌아줄건데 다음 x좌표와 다음 y 좌표를 구해주고 맵을 벗어나는지 확인해주고 visit을 체크해줄건데 visit은 몸이 있는 좌표에 true를 넣어주는 것이다. 뱀이 사과를 먹는 경우에 몸의 길이가 늘어나는데 이때 큐에 좌표를 넣어주고 v..

알고리즘/백준 2022.04.22

백준 13335 트럭 C++ [컴공과고씨]

https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 이 문제 같은 경우는 2개의 케이스로 나누어서 풀어주었다. 첫 번째는 트럭이 올라갈 때 다리의 무게가 버틸 수 있어 트럭이 올라갈 수 있는 경우와 트럭이 다리를 다 건넌 경우로 나누어 주었다. 트럭이 출발하면 큐에 넣을 건데 이 때 그 트럭의 무게와 언제 다리를 다 건너는지 도착 시간을 pair를 이용해서 넣어주는 것이 핵심이다. 큐를 쓰는 이유는 ..

알고리즘/백준 2022.04.21

백준 10799 쇠막대기 c++ [컴공과고씨]

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 첫 번째로 ) 나왔을 때 구별 해주어야할 것은 막대기의 끝인지 아니면 레이저인지 구별하는 것이다. ) 나오기 바로 직전이 ( 였다면 레이저이고 )이면 막대기의 끝이다. 이것을 이용하여 ( 나올때 카운트를 해준다. 그리고 ) 나왔을 때 (하나는 사라지는 것이므로 카운트 개수를 -1해준다. ) 나왔을 때 레이저라면 앞에 ( 개수를 세준수 만큼 잘린 막대기 개수가 나오므로 총 막대기 개수에 저장해준다. 만약 막대..

알고리즘/백준 2022.04.16

백준 9012 괄호 c++ [컴공과고씨]

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 이 문제를 보고 처음에는 당연히 queue를 떠올리기 어려울 수 있지만 한 번 직접 괄호 지우다 보면 queue가 떠올라야한다. 이런식으로 앞에 나온 ( 가 있다면 ) 나왔을 때 (을 지워주는 형식으로 할 것이다. 그런데 만약 남아있는 ( 있거나 ( 가 나오지 않았는데 ) 나온다면 그것도 잘못된 괄호이다. 그래서 큐를 이용하는 것이다. 먼저 ( 일 경우 큐에 push..

알고리즘/백준 2022.04.16
반응형