1193 - 분수찾기, 1225 - 이상한 곱셈, 1233 - 주사위

1193

분수찾기

• 1/1 1/2 2/1 3/1 2/2 1/3 1/4 2/3 3/2 4/1 5/1 ... 이 순서의 수열이 있을 때, X번째를 출력하라.

import java.util.Scanner;

public class bj1193_0127 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		sc.close();
		/**
		 * 11 / 12 21 / 31 22 13 / 14 23 32 41 / 51 ... 이렇게 합이 같은 수를 한 행에 놓는다고 할 때,
		 */
		int nri = 1; // 다음 행의 첫 인덱스
		int row = 0; // 이번 행의 분수 개수 (row+1은 분수 이루는 두 수의 합)
		while (nri <= X) {
			row++;
			nri += row;
		}
		int ri = nri - row; // 이번 행의 첫 인덱스
		int Xidx = X - ri; // X가 이번 행 몇 번째인지 (0=첫번째)
		if (row % 2 != 0) {
			System.out.println((row - Xidx) + "/" + (Xidx + 1));
		} else {
			System.out.println((Xidx + 1) + "/" + (row - Xidx));
		}

	}
}

• 코드 안에 설명이 있다.
• 중요한 건 하나하나 만들 필요가 없고, 몇 번째인지를 알면 바로 그걸 출력할 수 있는 알고리즘이 필요하다.

 

1225

이상한 곱셈

• 주어지는 n자리 수, m자리 수를 그냥 곱하지 않고, 각각 한 자리씩 뽑아 곱한다. 조합 가능한 모든 경우의 수의 곱을 모두 더한 값을 출력하라.
• 각 자리는 10,000자리를 넘지 않는 음이 아닌 정수이고, 0제외 0으로 시작하지 않는다.

import java.util.Scanner;

public class bj1225_0127 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String A = sc.next();
		String B = sc.next();
		sc.close();

		int Alen = A.length();
		int Blen = B.length();

		int[] Aa = new int[Alen];
		int[] Ba = new int[Blen];

		for (int i = 0; i < Alen; i++) {
			Aa[i] = A.charAt(i) - '0';
		}
		for (int i = 0; i < Blen; i++) {
			Ba[i] = B.charAt(i) - '0';
		}

		long res = 0;
		for (int i = 0; i < Alen; i++) {
			for (int j = 0; j < Blen; j++) {
				res += (long) Aa[i] * Ba[j];
			}
		}

		System.out.println(res);

	}
}

• 쉬워보이지만... 정답률이 낮은 이유가 있나보다.
• 마지막에 어이없는 함정이 있다...
• 10,000자리라서 int형이 아니라 String형으로 받는다 는 보면 알 수 있지만...
• 답이 int형으로 담아지지 않을 수 있다. 는 한참 고민하다가 알게됐다.
• 덕분에 연산 시 형변환에 대해서 더 알아봤는데 좀 적어보자면...
• int + int = int 이런 식으로 연산은 할 수 있고,
• int + long = long 이렇게 된다.
• 즉 둘 중 더 큰 쪽으로 맞춰진다.

 

1233

주사위

• 세 개의 주사위를 동시에 던졌을 때 가장 높은 빈도로 나오는 세 주사위의 합을 구하라.
• 3 2 3으로 주어지면, 1~3인 주사위 하나, 1~2인 주사위 하나, 1~3인 주사위 하나라는 뜻. 

import java.util.Scanner;

public class bj1233_0127 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		sc.close();

		// 0번 - 3개수 , 1번 - 4개수 , ...
		int[] arr = new int[a + b + c - 2];

		for (int i = 0; i < a; i++)
			for (int j = 0; j < b; j++)
				for (int k = 0; k < c; k++)
					arr[i + j + k]++;

		int tmp = 0;
		for (int i = 0; i < (a + b + c - 2) / 2 + 1; i++)
			if (arr[i] >= arr[i + 1]) {
				tmp = i;
				break;
			}

		System.out.println(tmp + 3);

	}
}

• 별거 아닌 것 처럼 생겨서는, 코드는 둘째치고 답을 어떻게 구할지 감이 안잡혔던 문제다.
• 그래서 답을 구하려고 노력했지만... 지쳐서 그냥 노가다로 3차원 배열을 만들어서 개수를 카운팅했다.
• 이렇게 하면 메모리 초과나 시간 초과가 나오겠지 했는데, 의외로 그냥 됐다.
• 이대로 지나치기엔 자존심이 허락하지 않아서... 다른 정답자에게로 힌트를 얻었지만..ㅋㅋ
• 3차원 배열을 선언하지 않고, 1차원 배열에 해답만 카운팅하면 최대값을 구할 수 있다는 점을 알았다.
• 그래서 새로 짠 코드가 위 코드인데, 수정 전과 후로 메모리랑 시간을 비교하려고 했는데...
• 메모리는 18208KB -> 17752KB
• 시간은 244ms -> 220ms
• 별로 차이가 없다... 그래서 조금 허망하다.