morenow
morenow
morenow
전체 방문자
오늘
어제
  • 분류 전체보기 (83)
    • 스프링부트와 AWS로 혼자 구현하는 웹 서비스 (5)
    • [MSA] Spring Cloud로 개발하는 마이.. (14)
    • Baekjoon Online Judge (40)
    • Programmers (11)
    • Spring Boot (7)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Spring Boot
  • write skew
  • lost update
  • HTTP Interface
  • Open Feign
  • 마법사 상어와 파이어스톰
  • 백준20058C++
  • HttpExchange
  • Feign Client
  • B Tree
  • copy up
  • Id Token
  • jwt
  • Refresh Token Refresh
  • B+ Tree
  • successHandler
  • dirty write
  • JWT단점
  • re-distribution
  • 백준 파이어스톰

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
morenow
Baekjoon Online Judge

[BOJ] 1744 : 수 묶기 (Java)

Baekjoon Online Judge

[BOJ] 1744 : 수 묶기 (Java)

2023. 10. 26. 02:54

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

 

1744번: 수 묶기

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

www.acmicpc.net

걸린 시간 : 25분 2초


알고리즘

두 수를 묶는다는 것은 곱한다는 것이다. 따라서 음수끼리 혹은 양수끼리 곱해야 한다.

즉, 음수가 짝수라면 작은 음수부터 차례대로 묶어가면 끝이다. 양수도 마찬가지로 짝수라면 큰 수부터 차례대로 묶어가면 된다.

만약 양수가 홀수라면 가장 작은 양수를 묶지 않고 즉시 더해주면 된다.

만약 음수가 홀수라면 가장 큰 음수를 즉시 더해주면 된다. 단, 만약 수열에 0이 존재할 경우 이 수는 0과 묶어서 날려버릴 수 있다.

 

여기까지는 많은 사람들이 생각했을 것이지만, 예상치 못한 부분이 하나 있었다. 양수에 1을 곱하면 자기 자신이 되어 커지지 않는다는 것이다. 즉 어떤 두 양수를 묶으면 (곱하면) 무조건 그 결과가 두 양수를 묶지 않았을 때보다 (더했을 때보다) 클 것이라고 예상했지만, 1이 존재하면 더하는 것이 더 큰 것이다.

따라서 수열을 입력받을 때, 1이 들어온다면 무조건 즉시 답에 1을 더해주고 배열에 넣지 않는다.

정답 코드

import java.io.*;
import java.util.*;
public class BOJ1744 {
static int N;
static List<Integer> negArr = new ArrayList<>();
static List<Integer> posArr = new ArrayList<>();
static boolean existZero = false;
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
int tmp = Integer.parseInt(br.readLine());
if (tmp == 1) {
answer++;
} else if (tmp < 0) {
negArr.add(tmp);
} else if (tmp > 0) {
posArr.add(tmp);
} else {
existZero = true;
}
}
Collections.sort(negArr);
posArr.sort(Collections.reverseOrder());
if (negArr.size() % 2 == 1) {
if (!existZero) {
answer += negArr.get(negArr.size()-1);
}
negArr.remove(negArr.size()-1);
}
if (posArr.size() % 2 == 1) {
answer += posArr.get(posArr.size()-1);
posArr.remove(posArr.size()-1);
}
for (int i = 0; i < negArr.size(); i += 2) {
answer += negArr.get(i) * negArr.get(i+1);
}
for (int i = 0; i < posArr.size(); i += 2) {
answer += posArr.get(i) * posArr.get(i+1);
}
System.out.println(answer);
}
}

'Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 9251 : LCS (Java)  (0) 2023.11.02
[BOJ] 1987 : 알파벳 (Java)  (1) 2023.10.26
[BOJ] 21608 : 상어 초등학교 (Java) with 정렬  (1) 2023.10.26
[BOJ] 1941: 영역 구하기 (Java)  (0) 2023.10.19
[BOJ] 1941: 소문난 칠공주 (Java) with 조합  (0) 2023.10.19
  • 알고리즘
  • 정답 코드
'Baekjoon Online Judge' 카테고리의 다른 글
  • [BOJ] 9251 : LCS (Java)
  • [BOJ] 1987 : 알파벳 (Java)
  • [BOJ] 21608 : 상어 초등학교 (Java) with 정렬
  • [BOJ] 1941: 영역 구하기 (Java)
morenow
morenow

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.