λ¬Έμ λ§ν¬
https://www.acmicpc.net/problem/2116
2116λ²: μ£Όμ¬μ μκΈ°
첫μ€μλ μ£Όμ¬μμ κ°μκ° μ λ ₯λλ€. κ·Έ λ€μ μ€λΆν°λ ν μ€μ νλμ© μ£Όμ¬μμ μ’ λ₯κ° 1λ² μ£Όμ¬μλΆν° μ£Όμ¬μ λ²νΈ μμλλ‘ μ λ ₯λλ€. μ£Όμ¬μμ μ’ λ₯λ κ° λ©΄μ μ νμ§ μ«μκ° κ·Έλ¦Ό1μ μλ
www.acmicpc.net
λμ΄λ
μκ°μ ν
2μ΄
λ¬Έμ
μ²μλ μ¬λ¬ μ’ λ₯μ μ£Όμ¬μλ₯Ό κ°μ§κ³ μκΈ° λμ΄λ₯Ό νκ³ μλ€. μ£Όμ¬μμ λͺ¨μμ λͺ¨λ ν¬κΈ°κ° κ°μ μ μ‘면체μ΄λ©° κ° λ©΄μλ 1λΆν° 6κΉμ§μ μ«μκ° νλμ© μ νμλ€. κ·Έλ¬λ λ³΄ν΅ μ£Όμ¬μμ²λΌ λ§μ£Ό 보λ λ©΄μ μ ν μ«μμ ν©μ΄ λ°λμ 7μ΄ λλ κ²μ μλλ€.
μ£Όμ¬μ μκΈ° λμ΄λ μλμμλΆν° 1λ² μ£Όμ¬μ, 2λ² μ£Όμ¬μ, 3λ² μ£Όμ¬μ, … μ μμλ‘ μλ κ²μ΄λ€. μμ λ λ€μκ³Ό κ°μ κ·μΉμ μ§μΌμΌ νλ€: μλ‘ λΆμ΄ μλ λ κ°μ μ£Όμ¬μμμ μλμ μλ μ£Όμ¬μμ μλ©΄μ μ νμλ μ«μλ μμ μλ μ£Όμ¬μμ μλ«λ©΄μ μ νμλ μ«μμ κ°μμΌ νλ€. λ€μ λ§ν΄μ, 1λ² μ£Όμ¬μ μλ©΄μ μ«μλ 2λ² μ£Όμ¬μ μλ«λ©΄μ μ«μμ κ°κ³ , 2λ² μ£Όμ¬μ μλ©΄μ μ«μλ 3λ² μ£Όμ¬μ μλ«λ©΄μ μ«μμ κ°μμΌ νλ€. λ¨, 1λ² μ£Όμ¬μλ λ§μλλ‘ λμ μ μλ€.
μ΄λ κ² μμ λμΌλ©΄ κΈ΄ μ¬κ°κΈ°λ₯μ΄ λλ€. μ΄ μ¬κ°κΈ°λ₯μλ 4κ°μ κΈ΄ μλ©΄μ΄ μλ€. μ΄ 4κ°μ μλ©΄ μ€μμ μ΄λ ν λ©΄μ μ«μμ ν©μ΄ μ΅λκ° λλλ‘ μ£Όμ¬μλ₯Ό μκ³ μ νλ€. μ΄λ κ² νκΈ° μνμ¬ κ° μ£Όμ¬μλ₯Ό μμλλ₯Ό κ³ μ ν μ± μμΌλ‘ 90λ, 180λ, λλ 270λ λ릴 μ μλ€. ν μλ©΄μ μ«μμ ν©μ μ΅λκ°μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ λ ₯
첫μ€μλ μ£Όμ¬μμ κ°μκ° μ λ ₯λλ€. κ·Έλ€μ μ€λΆν°λ ν μ€μ νλμ© μ£Όμ¬μμ μ’ λ₯κ° 1λ² μ£Όμ¬μλΆν° μ£Όμ¬μ λ²νΈ μμλλ‘ μ λ ₯λλ€. μ£Όμ¬μμ μ’ λ₯λ κ° λ©΄μ μ ν μ«μκ° κ·Έλ¦Ό 1μ μλ μ£Όμ¬μμ μ κ°λμμ A, B, C, D, E, Fμ μμλ‘ μ λ ₯λλ€. μ λ ₯λλ μ«μ μ¬μ΄μλ λΉμΉΈμ΄ νλμ© μλ€. μ£Όμ¬μμ κ°μλ 10,000κ° μ΄νμ΄λ©° μ’ λ₯κ° κ°μ μ£Όμ¬μλ μμ μ μλ€.
μΆλ ₯
첫μ€μ ν μλ©΄μ μ«μμ ν©μ΄ κ°μ₯ ν° κ°μ μΆλ ₯νλ€.
μ μΆλ ₯ μμ
μ λ ₯
5
2 3 1 6 5 4
3 1 2 4 6 5
5 6 4 1 3 2
1 3 6 2 4 5
4 1 6 5 2 3
μΆλ ₯
29
λ¬Έμ νμ΄ κ³Όμ
λ¬Έμ μ΄ν΄νκΈ°
λ¨Όμ μ£Όμ¬μ κ·Έλ¦Ό 1μ μ΄ν΄λ³΄μ.
Aμ λ°λ νΈμλ F, Bμ λ°λνΈμλ D, Cμ λ°λνΈμλ Eκ° μλ€λ κ²μ μ μ μλ€.
μ¦, μ§μ λ§μΆ°λ³΄λ©΄ A-F, B-D, C-Eμ΄λ€.
βλ§€λ² μ΅μ μ μ νμ νλ©΄ κ³Όμ° μ£Όμ¬μ μλ©΄μ μ«μμ ν©μ μ΅λκ°μ ꡬν μ μμκΉ?
λ΅μ "μλλ€"μ΄λ€.
κ·Έ μ΄μ λ 첫 λ²μ§Έ μ£Όμ¬μμμ μλ«λ©΄μΌλ‘ 1, μ¦ μ΅μμ μλ₯Ό μ ννλ€κ³ ν΄λ κ·Έμ μ§μΈ μκ° 6μΌλ‘ μ΅λμΌ μ μκΈ° λλ¬Έμ΄λ€.
λ°λΌμ 첫 λ²μ§Έ μ£Όμ¬μμ μλ«λ©΄μ 1λΆν° 6κΉμ§ κ³ μ μμΌ κ°λ©° ν΄λΉ κ²½μ°μ λ°λ₯Έ μ λ©΄μ μ΅λκ°μ ꡬν λ€μ κ·Έμ€ κ°μ₯ ν° κ°μ ꡬν΄μΌ νλ€.
μ λ ₯κ° μ μ₯νκΈ°
public class BOJ_2116 {
static int[][] dice;
static final int diceCount = 6;
static int[] diceMatch = {5, 3, 4, 1, 2, 0}; // A-F, B-D, C-E
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
dice = new int[N][diceCount];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < diceCount; j++) {
dice[i][j] = Integer.parseInt(st.nextToken());
}
}
}
}
μμμ μ΄ν΄λ΄€λ A-F, B-D, C-Eλ₯Ό μΈλ±μ€λ‘ νννλ©΄ 0-5, 1-3, 2-4κ° λμ΄ dicMatchλ³μμ μ μ₯νλ€.
κ·Έ ν μ΄μ€ forλ¬Έμ λλ©΄μ μ£Όμ¬μμ μ 보λ₯Ό diceλ³μμ μ μ₯νλ€.
첫 λ²μ§Έ μ£Όμ¬μμ μλ«λ©΄μ 1λΆν° 6κΉμ§ κ³ μ μν€λ©° ν΄λΉ κ²½μ° μ΄ν΄λ³΄κΈ°
int result = 0;
for (int i = 0; i < diceCount; i++) {
int bottom = dice[0][i];
...
for (int j = 1; j < N; j++) {
...
}
result = Math.max(totalMax, result);
}
forλ¬Έμ λλ©° 첫 λ²μ§Έ μ£Όμ¬μμ μλ«λ©΄μ κ³ μ μν¨λ€.
βκ·Έλ€μμΌλ‘λ μ΄λ€ μΌμ ν΄μΌ ν κΉ?
1. ν΄λΉ μ£Όμ¬μμ μλ«λ©΄μ λ°λ₯Έ λ€μ μ£Όμ¬μμ μλ«λ©΄μ indexλ₯Ό ꡬνλ€.
2. λ€μ μ£Όμ¬μ μλ«λ©΄μ indexλ₯Ό ν΅ν΄ ν΄λΉ μ£Όμ¬μμ μλ©΄μ indexμ μλ«λ©΄μ indexλ₯Ό μ μΈν indexλ₯Ό μ΄ν΄λ³΄λ©° μ΅λκ°μ ꡬνμ¬ μλ©΄μ μ΅λκ°μ ꡬνλ€.
μ¦, 첫 λ²μ§Έ μ£Όμ¬μμ μλ«λ©΄μ κ³ μ μν€λ©΄ λ€μ 쑰건μ λ°λΌ λ€μ μ£Όμ¬μμ μλ©΄κ³Ό μλ«λ©΄μ μ ν΄μ§κ² λλ€.
μλ‘ λΆμ΄ μλ λ κ°μ μ£Όμ¬μμμ μλμ μλ μ£Όμ¬μμ μλ©΄μ μ νμλ μ«μλ μμ μλ μ£Όμ¬μμ μλ«λ©΄μ μ νμλ μ«μμ κ°μμΌ νλ€.
λν λ¬Έμ μ λ€μκ³Ό κ°μ΄ μμλλ₯Ό κ³ μ ν μ± μμΌλ‘ λ릴 μ μλ€λ μ‘°κ±΄μ΄ μμΌλ―λ‘ λ§€ μ£Όμ¬μλ§λ€ μλ©΄κ³Ό μλ«λ©΄μ μ μΈν κ° μ€ μ΅λκ°μ μ°ΎμΌλ©° λν΄μ£Όλ©΄ λλ€.
μ΄λ κ² νκΈ° μνμ¬ κ° μ£Όμ¬μλ₯Ό μμλλ₯Ό κ³ μ ν μ± μμΌλ‘ 90λ, 180λ, λλ 270λ λ릴 μ μλ€.
index+1λ²μ§Έ μ£Όμ¬μ μλ«λ©΄ μ«μλ‘ λ€μ μ£Όμ¬μ μλ«λ©΄ index μ°ΎκΈ°
static int findNextBottomIndex(int index, int bottom) {
int nBottomIndex = 0;
for (int i = 0; i < diceCount; i++) {
if (dice[index][i] == bottom) {
nBottomIndex = diceMatch[i];
break;
}
}
return nBottomIndex;
}
첫 λ²μ§Έ μ£Όμ¬μμ μλ«λ©΄μ κ³ μ μν€κΈ° λλ¬Έμ λ λ²μ§ΈλΆν° λ§μ§λ§ μ£Όμ¬μκΉμ§ λ°λ³΅λ¬Έμ λλ©° μ£Όμ¬μμ 6λ©΄μ μ΄ν΄λ³΄κ³ bottomκ³Ό κ°μ μκ° λμ€λ©΄ ν΄λΉ μ£Όμ¬μμ μλ©΄μ indexλ₯Ό μκ² λλ€. diceMatchλ°°μ΄μ ν΅ν΄ ν΄λΉ μ£Όμ¬μμ μλ«λ©΄ indexλ₯Ό μ°Ύμ ν return νλ€.
μλ«λ©΄ indexλ₯Ό ν΅ν΄ μλ©΄μ μ΅λκ° μ°ΎκΈ°
static int findMax(int index, int bottomIndex) {
int max = 0;
for (int i = 0; i < diceCount; i++) {
if (i == bottomIndex || i == diceMatch[bottomIndex]) {
continue;
}
if (max < dice[index][i]) {
max = dice[index][i];
}
}
return max;
}
ν΄λΉ μ£Όμ¬μμ μλ«λ©΄κ³Ό μλ©΄μ indexλ₯Ό μ μΈν κ° μ€ λ°λ³΅λ¬Έμ λλ©° μ΅λκ°μ μ°Ύμλ΄κ³ μ΄λ₯Ό return νλ€.
μ΅μ’ μ½λ
public class BOJ_2116 {
static int[][] dice;
static final int diceCount = 6;
static int[] diceMatch = {5, 3, 4, 1, 2, 0}; // A-F, B-D, C-E
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
dice = new int[N][diceCount];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < diceCount; j++) {
dice[i][j] = Integer.parseInt(st.nextToken());
}
}
int result = 0;
for (int i = 0; i < diceCount; i++) {
int bottom = dice[0][i];
int totalMax = findMax(0, i);
for (int j = 1; j < N; j++) {
int nBottomIndex = findNextBottomIndex(j, bottom);
totalMax += findMax(j, nBottomIndex);
bottom = dice[j][nBottomIndex];
}
result = Math.max(totalMax, result);
}
System.out.println(result);
}
// index+1λ²μ§Έ μ£Όμ¬μ μλ«λ©΄ μ«μλ‘ λ€μ μ£Όμ¬μ μλ«λ©΄ index μ°ΎκΈ°
static int findNextBottomIndex(int index, int bottom) {
int nBottomIndex = 0;
for (int i = 0; i < diceCount; i++) {
if (dice[index][i] == bottom) {
nBottomIndex = diceMatch[i];
break;
}
}
return nBottomIndex;
}
static int findMax(int index, int bottomIndex) {
int max = 0;
for (int i = 0; i < diceCount; i++) {
if (i == bottomIndex || i == diceMatch[bottomIndex]) {
continue;
}
if (max < dice[index][i]) {
max = dice[index][i];
}
}
return max;
}
}
첫 λ²μ§Έ μ£Όμ¬μμ μλ«λ©΄μ 1λΆν° 6κΉμ§ κ³ μ μν€λ©° μ λ©΄μ μ΅λκ°μ ꡬν λ€ κ·Έμ€ κ°μ₯ ν° κ°μ μΆλ ₯νλ€.
'π―PS - Baekjoon, etc > ꡬν' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[μ΄κ²μ΄ μ½λ© ν μ€νΈλ€] κ²μ κ°λ° (Java) (0) | 2023.03.06 |
---|---|
[μ΄κ²μ΄ μ½λ©ν μ€νΈλ€] μμ€μ λμ΄νΈ (Java) (0) | 2023.03.04 |
λκΈ