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
- 별로 차이가 없다... 그래서 조금 허망하다.
'PS - BOJ' 카테고리의 다른 글
1408 - 24 (0) | 2022.01.31 |
---|---|
1292, 1316, 1357 - 쉽게 푸는 문제, 그룹 단어 체커, 뒤집힌 덧셈 (0) | 2022.01.30 |
1157 - 단어 공부 (0) | 2022.01.27 |
1100, 1110, 1159 - 하얀 칸, 더하기 사이클, 농구 경기 (0) | 2022.01.27 |
1026, 1037, 1085 - 보물, 약수, 직사각형에서 탈출 (0) | 2022.01.26 |