114. 좋다 (백준 1253) [JAVA]

114. 좋다 (백준 1253) [JAVA]

문제

문제 링크 : https://www.acmicpc.net/problem/1253

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

풀이

전체 숫자가 2000개이므로, 모든 덧셈 조합을 만들어보면 10C2 = 1000*1999개이다.

여기서 이제 숫자가 속해있는지를 탐색해야 하는데

단순히 배열을 사용한다면, n번을 더 탐색해야 해서 횟수가 많아지게 된다.

따라서 복잡하더라도 해시맵을 사용했다.

이때 해시맵을 사용하게 된다면 발생하는 문제가, 0을 더해주는 경우 자기 자신에 관한 처리이다.

0 0 은 자기 자신을 포함하여 불가능하다.

반면 0 0 0 은 0(1) + 0(2) -> 0(3)이 가능하고, 조합을 돌려주면 되니깐 3개 모두 가능하다.

1 0 2의 경우 자기 자신을 포함하기 때문에 1, 2가 불가능하다.

반면 1 0 1의 경우 1(1) + 0 -> 1(2)로 가능하기 때문에 1이 두개 모두 가능하다.

둘다 0인경우 -> 0이 3개가 아니면 더해주지 않기 하나가 0인 경우 -> 나머지 하나가 2개가 아니면 더해주지 않기

처리가 끝난 키값은 삭제함으로써 중복을 방지하였다.

코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Main { static int N; static HashMap maps = new HashMap<>(); static int[] goods; static int answer = 0; /** * 2000C2*2000 = 2000*1999*1000 **/ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()); goods = new int[N]; for(int i=0; i= 3){ answer = answer + add; maps.remove(sum); } } //1개만 0일때 = 2이상 else if(goods[i] == 0 || goods[j] == 0){ if(add >= 2){ answer = answer + add; maps.remove(sum); } } else{ answer = answer + add; maps.remove(sum); } } } } System.out.println(answer); } }

결과

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.

언제든지 댓글로 의견을 남겨주세요!

반응형

from http://howtolivelikehuman.tistory.com/258 by ccl(A) rewrite - 2021-09-23 23:27:07