πŸ… SAMSUNG λͺ¨μ˜κ³ μ‚¬ : λ‹¨λ°±μ§ˆ 사λƒ₯κΎΌ

문제

μžμ‹ μ˜ λͺΈμ΄ ν—ˆμ•½ν•˜λ‹€κ³  μƒκ°ν•œ 정택은 κ°•ν•΄μ§€κΈ°μœ„ν•΄ μš΄λ™μ„ ν•˜κΈ° μ‹œμž‘ν–ˆλ‹€. μ•Œκ³ λ¦¬μ¦˜ ν”ΌνŠΈλ‹ˆμŠ€ μ„Όν„°μ˜ μ„Όν„°μž₯인 μ’…λ―Όμ˜ 쑰언에 따라 β€œλ¨ΉλŠ” 것 κΉŒμ§€ μš΄λ™μ΄λ‹€.” λΌλŠ” 철칙을 잘 λ”°λ₯΄κ³  μžˆλ‹€. μ „λ‚  λ¬΄λ¦¬ν•˜κ²Œ μš΄λ™ν•œ μ—¬νŒŒλ‘œ λŠ¦μž μ„ μžκ²Œλ˜μ–΄, 였늘 먹을 λ‹¨λ°±μ§ˆ λ„μ‹œλ½μ„ μ±™κΈΈ μ—¬μœ κ°€ μ—†μ—ˆλ‹€. μ–΄μ œ λ¬΄λ¦¬ν•˜κ²Œ μš΄λ™ν•œ 것이 μ•„κΉŒμš΄ 정택은 사무싀 κ·Όμ²˜μ— μžˆλŠ” νŽΈμ˜μ μ„ 돌며 얻을 수 μžˆλŠ” μ΅œλŒ€μ˜ λ‹¨λ°±μ§ˆμ„ ν™•λ³΄ν•˜λ €κ³  ν•œλ‹€. 같은 λ‹¨λ°±μ§ˆ 함양을 가진 μ œν’ˆμ€ λ™μΌν•œ μ œν’ˆμ΄κ³ , 같은 λ„μ‹œλ½μ„ μ—¬λŸ¬ 번 먹으면 μ§ˆλ¦¬κΈ°λ•Œλ¬Έμ— μ„œλ‘œ λ‹€λ₯Έ μ œν’ˆμ„ 톡해 λ‹¨λ°±μ§ˆμ„ μ„­μ·¨ν•˜κ³ μž ν•œλ‹€. 힘이 μƒμŠΉν•˜κ³ μžν•˜λŠ” 정택은 νŽΈμ˜μ μ„ β€˜+’ λͺ¨μ–‘μœΌλ‘œ μˆœνšŒν•˜λ €κ³  ν•œλ‹€.

protein1.png
protein2.png

μœ„μ™€ 같이 편의점 정보가 μ‘΄μž¬ν•œλ‹€κ³  ν–ˆμ„ λ•Œ, 각 칸에 ν•΄λ‹Ήν•˜λŠ” μˆ«μžλŠ” ν•΄λ‹Ή νŽΈμ˜μ μ—μ„œ 얻을 수 μžˆλŠ” λ‹¨λ°±μ§ˆμ˜ g 수 이닀. 첫 번째 κ·Έλ¦Όμ—μ„œ 얻을 수 μžˆλŠ” μ„œλ‘œ λ‹€λ₯Έ μ’…λ₯˜μ˜ λ‹¨λ°±μ§ˆ λ„μ‹œλ½ κ°œμˆ˜λŠ” 4개이며, 얻을 수 μžˆλŠ” λ‹¨λ°±μ§ˆ g μˆ˜λŠ” 7+2+10+9 둜 28 이닀. 두 번째 κ·Έλ¦Όμ—μ„œ 얻을 수 μžˆλŠ” μ„œλ‘œ λ‹€λ₯Έ μ’…λ₯˜μ˜ λ‹¨λ°±μ§ˆ λ„μ‹œλ½ κ°œμˆ˜λŠ” 5개이며, 얻을 수 μžˆλŠ” λ‹¨λ°±μ§ˆ g μˆ˜λŠ” 1+3+4+9+10 둜 27 이닀.

순회 경둜의 경우 λ§Œμ•½ 쀑앙을 기점으둜 봀을 λ•Œ, μƒν•˜μ’Œμš° 경둜의 길이λ₯Ό μ„œλ‘œ 달리할 수 μžˆλ‹€. μ΄λ•Œ 경둜의 길이 μ΅œμ†Ÿκ°’μ€ μƒν•˜μ’Œμš° 각각 λͺ¨λ‘ 1둜 κ³ μ •ν•œλ‹€. 즉, ν•˜λ‚˜μ˜ 편의점만 λ“€λ₯Ό 수 μ—†κ³ , 직선 ν˜•νƒœ, β€˜γ„±β€™, β€˜γ„΄β€™ λ“±μ˜ λͺ¨μ–‘μœΌλ‘œ 순회λ₯Ό ν•  수 μ—†λ‹€λŠ” 것이닀. 예λ₯Ό λ“€λ©΄, λ‹€μŒκ³Ό 같이 λ‹€μ–‘ν•˜κ²Œ μ‘΄μž¬ν•  수 μžˆλ‹€.

protein3.png
protein4.png
protein5.png
protein6.png
protein7.png

μ‹œμž‘ μ§€μ μ—μ„œ μΆœλ°œν•˜μ—¬ λ‹€μ‹œ μ‹œμž‘ μ§€μ μœΌλ‘œ λŒμ•„μ˜¨λ‹€κ³  ν–ˆμ„ λ•Œ, N * N 의 편의점 λ‹¨λ°±μ§ˆ λ„μ‹œλ½ μ •λ³΄μ—μ„œ κ°€μž₯ 많이 얻을 수 μžˆλŠ” λ‹¨λ°±μ§ˆ ν•¨λŸ‰μ˜ 합을 κ΅¬ν•΄λ³΄μž.

편의점 정보가 μ£Όμ–΄μ‘Œμ„ λ•Œ, 닡을 κ΅¬ν•˜λŠ” 과정은 λ‹€μŒκ³Ό κ°™λ‹€. (총 6가지가 μ‘΄μž¬ν•˜λŠ” 것은 μ•„λ‹ˆλ©°, λͺ‡ 가지 κ²½μš°λŠ” μƒλž΅λ˜μ—ˆλ‹€.)

protein8.png
protein9.png
protein10.png
protein11.png
protein12.png
protein13.png

λ§ˆμ§€λ§‰ κ·Έλ¦Όμ—μ„œ μ–»μ–΄μ§€λŠ” 숫자의 ν•© 1+2+3+5+6+7+8 인 32 κ°€ 정닡이닀.

μž…λ ₯

첫 번째 쀄에 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 개수 T(5 ≀ T ≀ 50) κ°€ 주어진닀. 각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 첫째 쀄에 N(3 ≀ N ≀ 20) 이 주어지고, N 개의 쀄에 걸쳐 N 개의 μˆ«μžκ°€ 곡백을 톡해 κ΅¬λΆ„ν•˜μ—¬ μž…λ ₯λœλ‹€. 각각의 μž…λ ₯λ˜λŠ” μˆ«μžλŠ” 1 λΆ€ν„° 100 을 ν¬ν•¨ν•œ μ •μˆ˜μ΄λ‹€.

좜λ ₯

각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ— ν•΄λ‹Ήν•˜λŠ” 결과값을 ν•œ 쀄에 ν•˜λ‚˜μ”© β€œ#t result” 포맷으둜 좜λ ₯ν•œλ‹€. (tλŠ” 1λΆ€ν„° TκΉŒμ§€μ˜ μ •μˆ˜μ΄λ‹€)

5
4
7 8 6 10
9 2 7 1
6 5 1 3
1 7 5 9
10
7 7 5 8 3 1 5 6 4 4
1 8 4 4 4 6 3 7 9 3
8 8 6 7 3 8 5 4 3 7
3 4 1 6 4 3 5 3 2 7
9 9 1 8 3 9 6 4 2 2
4 5 5 7 4 7 1 8 9 6
1 7 7 8 5 2 6 1 5 2
3 9 6 1 8 2 3 4 5 4
2 1 1 2 9 6 1 4 6 6
9 2 4 6 7 1 4 3 8 6
8
4 7 1 6 8 5 8 7
4 5 6 1 9 1 1 8
7 2 1 4 1 7 1 1
3 8 6 2 5 2 5 1
9 8 8 4 8 7 8 9
1 2 2 4 3 3 9 4
3 9 3 2 2 8 5 9
4 3 4 2 3 4 6 6
6
5 3 9 3 7 5
9 4 9 1 5 4
3 3 7 8 1 6
6 8 7 3 3 3
1 3 9 8 5 6
1 1 3 7 6 3
4
7 7 3 6
1 3 2 1
9 6 1 8
2 2 2 2
#1 32
#2 45
#3 45
#4 39
#5 36

μ œν•œ 사항

  • μ œν•œμ‹œκ°„ : 3초

풀이

λ¬Έμ œμ—μ„œ μ œμ‹œλœ 쑰건을 정리해보면 μ•„λž˜μ™€ κ°™λ‹€.

  1. 같은 λ‹¨λ°±μ§ˆ 함양을 가진 μ œν’ˆμ€ λ™μΌν•œ μ œν’ˆμ΄κ³ , 같은 λ„μ‹œλ½μ„ μ—¬λŸ¬ 번 먹으면 μ§ˆλ¦¬κΈ°λ•Œλ¬Έμ— μ„œλ‘œ λ‹€λ₯Έ μ œν’ˆμ„ 톡해 λ‹¨λ°±μ§ˆμ„ μ„­μ·¨ν•˜κ³ μž ν•œλ‹€.

    • μ„ νƒλœ 편의점(μΉΈ)의 λ‹¨λ°±μ§ˆ 함양(κ°’) 쀑 같은 것은 μ œμ™Έν•˜κ³  ν•©μ‚°ν•΄μ•Ό ν•œλ‹€.
  2. 정택은 νŽΈμ˜μ μ„ β€˜+’ λͺ¨μ–‘μœΌλ‘œ μˆœνšŒν•˜λ €κ³  ν•œλ‹€.

    • λ”°λΌμ„œ 첫 쀄과 λ§ˆμ§€λ§‰ 쀄은 μ œμ™Έν•œ ν›„ μˆœνšŒν•΄μ•Ό ν•œλ‹€. μ œν•œμ‹œκ°„μ΄ 3초둜 μ—¬μœ λ‘œμš΄ 편이기 λ•Œλ¬Έμ— 전체 순회λ₯Ό μ‹œλ„ν•΄λ„ 될 것 κ°™λ‹€.
      κ°€λŠ₯ν•œ λͺ¨λ“  경우의 수λ₯Ό μˆœνšŒν•΄ κ°€μž₯ 큰 값을 μ°Ύμ•„ ν•΄κ²°ν–ˆλ‹€.
  3. 정택은 사무싀 κ·Όμ²˜μ— μžˆλŠ” νŽΈμ˜μ μ„ 돌며 얻을 수 μžˆλŠ” μ΅œλŒ€μ˜ λ‹¨λ°±μ§ˆμ„ ν™•λ³΄ν•˜λ €κ³  ν•œλ‹€.

    • μ΅œλŒ€μ˜ λ‹¨λ°±μ§ˆμ„ 확보해야 ν•˜λ―€λ‘œ κ°€μž₯ 큰 값을 μ°Ύμ•„μ•Ό ν•œλ‹€.
#include <iostream>
using namespace std;

//쀑볡을 μ œμ™Έν•œ λͺ¨λ“  κ°’μ˜ 합을 κ΅¬ν•˜λŠ” ν•¨μˆ˜
int uniqueSum(int arr[], int length){
  int temp[length]; //쀑볡을 μ œμ™Έν•œ 값듀을 μ €μž₯ν•  λ°°μ—΄
  int count = 0; //쀑볡을 μ œμ™Έν•œ κ°’μ˜ 개수(인덱슀용)
  int sum = 0; //쀑볡을 μ œμ™Έν•œ κ°’λ“€μ˜ ν•©

  bool isNew; //쀑볡 μ—¬λΆ€λ₯Ό νŒλ‹¨ν•˜λŠ” λ³€μˆ˜
  for(int i = 0; i < length; ++i){ //λ°°μ—΄μ˜ λͺ¨λ“  값을 순회
    isNew = true;
    //쀑볡을 μ œμ™Έν•œ κ°’λ“€μ˜ 배열을 μˆœνšŒν•˜λ©° 쀑볡 μ—¬λΆ€λ₯Ό νŒλ‹¨
    for(int j = 0; j < count; ++j){
      if(temp[j] == arr[i]){
        isNew = false;
        break;
      }
    }
    if(isNew){ //쀑볡이 μ•„λ‹ˆλΌλ©΄
      temp[count++] = arr[i]; //쀑볡을 μ œμ™Έν•œ κ°’λ“€μ˜ 배열에 μΆ”κ°€
      sum += arr[i]; //쀑볡을 μ œμ™Έν•œ κ°’λ“€μ˜ 합에 μΆ”κ°€
    }
  }
  return sum;
}

int test(){
  //ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ κ°€λ‘œ μ„Έλ‘œ 길이(N) μž…λ ₯ λ°›κΈ°
  int n;
  cin >> n;

  //ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 편의점 정보 μž…λ ₯ λ°›κΈ°
  int arr[n][n];
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      cin >> arr[j][i];
    }
  }

  //ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 편의점 정보λ₯Ό μˆœνšŒν•˜λ©° μ΅œλŒ€μ˜ λ‹¨λ°±μ§ˆ 함양을 κ΅¬ν•˜κΈ°
  int temp[n + n], current, max = -1;
  for(int i = 1; i < n - 1; ++i){ //첫 쀄과 λ§ˆμ§€λ§‰ 쀄은 μ œμ™Έ
    for(int j = 1; j < n - 1; ++j){ //첫 쀄과 λ§ˆμ§€λ§‰ 쀄은 μ œμ™Έ
      for(int k = 0; k < n; ++k){ //κ°€λ‘œ μ„Έλ‘œ λ°©ν–₯ 순회λ₯Ό ν•œλ²ˆμ— μ§„ν–‰ν•˜κ³  temp λ³€μˆ˜μ— μž…λ ₯
        temp[k] = arr[i][k];
        temp[k + n] = arr[k][j];
      }
      current = uniqueSum(temp, n + n); //쀑볡을 μ œμ™Έν•œ λͺ¨λ“  κ°’μ˜ 합을 ꡬ함
      if(max < current){
        max = current; //μ΅œλŒ€κ°’μ„ κ°±μ‹ 
      }
    }
  }

  return max;
}

int main() {
  //ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 수(T) μž…λ ₯ λ°›κΈ°
  int t;
  cin >> t;

  //ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 수만큼 ν…ŒμŠ€νŠΈλ₯Ό 반볡
  for(int i = 0; i < t; ++i){
    cout << "#" << (i + 1) << " " << test() << endl;
  }

  return 0;
}