알고리즘/자료구조

[백준] 1940 주몽 (투 포인터) - Java

2023. 5. 14. 00:06
목차
  1. 문제 상황
  2. 입력
  3. 출력
  4. 접근법
  5. 문제 풀이

 

 

1940번: 주몽

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고

www.acmicpc.net

 

문제 상황

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

 

접근법

  • 정렬 후 투포인터 사용
  • 시간복잡도 O(NLogN)

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int count = 0;
        int sum;

        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                sum = arr[i] + arr[j];
                if (sum == M) count++;
            }

        }

        System.out.println(count);
    }
}
저작자표시 (새창열림)

'알고리즘 > 자료구조' 카테고리의 다른 글

[백준] 12891 DNA 비밀번호 (슬라이딩 윈도우) - Java  (1) 2023.05.14
[백준] 1253 좋다 (투 포인터) - Java  (0) 2023.05.14
[백준] 2018 수들의 합 5 (투 포인터) - Java  (0) 2023.05.13
[백준] 10986 나머지 합 (누적 합) - Java  (0) 2023.05.13
[백준] 11660 구간 합 구하기 5 (누적 합) - Java  (0) 2023.05.13
  1. 문제 상황
  2. 입력
  3. 출력
  4. 접근법
  5. 문제 풀이
'알고리즘/자료구조' 카테고리의 다른 글
  • [백준] 12891 DNA 비밀번호 (슬라이딩 윈도우) - Java
  • [백준] 1253 좋다 (투 포인터) - Java
  • [백준] 2018 수들의 합 5 (투 포인터) - Java
  • [백준] 10986 나머지 합 (누적 합) - Java
jny0
jny0
성장일기
jny0
J N Y 0
jny0
  • 분류 전체보기 (192)
    • 트러블슈팅 (6)
    • Java (22)
    • HTML, CSS , JavaScript (7)
    • MySQL, DBMS (9)
    • GIT (6)
    • 객체지향의 사실과 오해 (3)
    • 자바 ORM 표준 JPA 프로그래밍 (13)
    • 알고리즘 (114)
      • 자료구조 (59)
      • 수학 (11)
      • 정렬 (2)
      • 그리디 (3)
      • DP (4)
      • 그래프 (3)
      • 탐색 (9)
      • 재귀 (2)
      • 문자열 (9)
      • 기타 (12)
    • CS (10)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기
  • 관리

공지사항

인기 글

태그

  • 누적합
  • MySQL
  • method
  • db
  • DP
  • 알고리즘
  • JS
  • 그리디
  • JPA
  • codeup
  • 영상후기
  • 프로그래머스
  • Java
  • 스택
  • 백준
  • 구현
  • BFS
  • git
  • 투포인터
  • 자료구조

최근 댓글

최근 글

hELLO · Designed By 정상우.
jny0
[백준] 1940 주몽 (투 포인터) - Java
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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