새소식

알고리즘/문제

[BOJ/백준 - 1744] 수 묶기

  • -

문제 출처: https://www.acmicpc.net/problem/1744

 

1744번: 수 묶기

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에

www.acmicpc.net



 

숫자를 오름차순으로 정렬한다

 

음수, 0, 1, 양수 부분을 나눠서 큐에 저장한다.

양수부분 큐는 poll을 했을때 제일 큰 값이 올 수 있도록 셋팅해준다

 

음수부분 큐를 하나씩 빼면서 2개 빠질때마다 곱해서 답에 더해준다

음수부분 큐가 비었을 경우 음수 1개가 남아 있다면

0부분 큐를 확인해 0이 존재하면 그냥 넘어가고 0이 존재하지 않으면 나머지 음수1개를 답에 더해준다

 

양수부분 큐를 하나씩 빼면서 2개 빠질때마다 곱해서 답에 더해준다

양수부분 큐가 비었을 경우 양수 1개가 남아 있다면 답에 더해준다

 

1부분 큐를 꺼내면서 답에 더해준다

 

코드에 있는 checker 배열은 숫자가 2개 들어오는지 확인 하고

큐에서 다 제거되었을 때 1개가 남아있는지 확인하는 배열이다

'알고리즘 > 문제' 카테고리의 다른 글

[BOJ/백준 - 10845] 큐  (0) 2022.01.11
[BOJ/백준 - 15829] Hashing  (0) 2022.01.11
[BOJ/백준 - 13904] 과제  (0) 2022.01.11
[BOJ/백준 - 1339] 단어 수학  (0) 2022.01.10
[BOJ/백준 - 1946] 신입 사원  (0) 2022.01.10
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.