기록방

👉 문제링크 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 🔸 문제 분석 🔸 N개의 수에서 서로 다른 두 수로 만들 수 있는 수의 개수를 출력한다. 인덱스가 다르면 값이 같아도 다른 수이다. 시간 복잡도 N의 개수가 최대값 2,000이라 가정해도 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 한다. (N^2 를 사용하면 다시 N번 반복해서 최종 시간 복잡도는 N^3가 되기 때문) 좋은 수 하나를 찾는 알고리즘은 최소 O(nlongn)이어야 한다. 정렬과 투 포인터 알고리즘 사용 단, 정렬된 데이터에서 자기 자신을 좋은..

👉 문제링크 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 🔸 문제 분석 🔸 n개의 수를 입력받고, 그 중에 2개의 합이 m이 되는 경우의 수를 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[..

👉 문제링크 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 🔸 문제 분석 🔸 1부터 N이하의 수들의 합이 N이 나오는 경우의 수를 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) th..

👉 문제링크 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 🔸 문제 분석 🔸 n개의 입력되는 숫자의 부분 구간 합이 m으로 나누어 떨어지는 경우의 수를 출력한다. n은 100만, m은 100이다. 구간 합을 매번 계산하면 시간이 부족하므로 구간 합 배열을 미리 계산한다. 구간 합 배열 공식 : S[i] = S[i-1] + A[i] 배열에서 구간 합 구하기 ( i ~ j ) : S[j] - S[i-1] 나머지도 미리 계산해 두는 것이 핵심 아이디어 (A + B) ..

👉 문제링크 1384번: 메시지 그룹 번호를 "Group 1"과 같이 출력함으로써 출력을 시작합니다. 그 다음 줄부터 누가(A) 누구(B)에게 나쁜 말을 했는지 "A was nasty about B"로 한 줄씩 출력합니다. 나쁜 말이 여러 개라면, 입력받은 순 www.acmicpc.net 🔸 문제 분석 🔸 인원수 n이 입력된다. 왼쪽으로 넘기는 롤링페이퍼 후 긍정 메시지와 부정 메시지 결과가 입력된다. 그룹마다 누가 누구에게 부정 메시지를 적었는지 출력한다. n으로 0이 입력될 때까지 반복한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.A..