미녀비

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

문제

입력 값으로 N개의 숫자들이 주어지는데 하나의 수가 자신을 제외한 2개의 수의 합으로 나타낸다면 '좋다'라고 합니다.

예를들어 입력값인 1 2 3 4 5 6 7 8 9 10 중 3은 1+2, 4는 1+3과 같은 경우입니다.

문제풀이

예제에는 보기 좋게 숫자가 정렬되어 나오지만 다른 케이스에서도 편한 계산을 위해 배열의 값을 정렬해줍니다.

이 문제는 투포인터를 사용하여 풀이했고 몇 가지 주의해야할 점이 있습니다.

1. 같은 값이 입력값으로 들어올 수 있다.

2. 자기 자신을 좋은 수 만들기에 포함하면 안된다.

저의 경우는 1번 케이스를 생각하지 않고 배열의 1,2 번 값은 필요 없는 값으로 생각해서 한 차례 틀렸습니다.

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());

		StringTokenizer st = new StringTokenizer(br.readLine());
		int arr[] = new int [N];
		
		for(int i = 0; i<N; i++) {
			 arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);

		int count = 0;
		
		for(int i = 0; i<N;i++) {
			int sIndex = 0;
			int eIndex = N-1;
			
			while(sIndex != eIndex) {
				if( arr[sIndex]+arr[eIndex] == arr[i]) {
					if(sIndex != i && eIndex != i) {
						count++;
						break;
					}else if (sIndex==i) {
						sIndex++;
					}else if (eIndex==i) {
						eIndex--;
					}
				}else if( arr[sIndex]+arr[eIndex] > arr[i]) {
					eIndex--;
				}else {
					sIndex++;
				}
					
			}
			
		}
		
		System.out.println(count);
	}
}

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

문제

재료의 개수 N이 주어지며 갑옷이 완성되는 번호의 합 M 이 주어진다.

이제 재료로 주어지는 N개의 숫자에서 2개의 합이 M이 되는 경우를 찾으면 된다.

문제풀이

두 재료 번호의 합을 비교해야 하므로 주어지는 재료들이 정렬되어있을 경우 더 간편하게 비교가 가능합니다.

배열을 오름차순으로 정렬 후 투 포인터 방법을 사용하여 시작, 종료인덱스를 지정하며 아래처럼 인덱스 규칙을 만듭니다.

1. 시작 인덱스와 종료인덱스 값의 재료의 합이 M보다 작다면 시작인덱스를 다음칸으로 옮겨줍니다.

2. 시작 인덱스와 종료인덱스 값의 재료의 합이 M보다 크다면 종료인덱스를 다음칸으로 옮겨줍니다.

3. 재료의 합이 M과 같다면 결과 값을 1개 추가하고 시작 인덱스를 다음칸으로 옮겨 다음 경우의 수를 탐색합니다.

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 startIndex = 0;
		int endIndex = N-1;
		
		int count = 0;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int arr[] = new int[N];
		
		for(int i = 0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		while(startIndex < endIndex) {
			
			if(arr[startIndex] + arr[endIndex] < M) {
				startIndex++;
			}else if(arr[startIndex] + arr[endIndex] > M) {
				endIndex--;
			}else {
				count++;
				startIndex++;
			}
		}
		
		System.out.println(count);
		
	}

}

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

문제

입력으로 주어진 자연수 N을 1개 이상의 자연수들의 합으로 만들 수 있는 가짓수를 구하는 문제이다.

예제로 주어진 15의 경우 1+2+3+4+5 / 4+5+6 / 7+8 / 15 이렇게 4가지 경우로 만들 수 있습니다.

문제풀이

투 포인터 방법을 사용해서 시작,종료 인덱스를 투 포인터로 지정했고, 인덱스 변화에는 3가지 규칙이 있습니다.

1. N이 sum보다 크다면 종료 인덱스를 다음칸으로 옮겨주고 해당 값을 sum에 추가해줍니다.

2. sum이 N보다 크다면 sum에서 시작 인덱스 값을 빼 주고 시작 인덱스를 다음칸으로 옮겨줍니다.

3. sum과 N이 같다면 경우의 수를 하나 추가하고 종료 인덱스를 다음칸으로 옮겨 다음 경우의 수를 탐색합니다.

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 sIndex = 1;
		int eIndex = 1;
		int sum = 1;
		int count = 1;
		
		while(eIndex!=N) {
			if (sum<N) {
				eIndex++;
				sum += eIndex;
			}else if(sum>N) {
				sum = sum - sIndex;
				sIndex++;
			}else {
				count++;
				eIndex++;
				sum = sum + eIndex;
			}
			
		}
		System.out.println(count);		
	}
}