3-P 꽃길 반복문 풀이와 취업을 위한 코테 접근법..

안녕하세요 큰돌님!

백준 알고리즘 문제를 풀다 보면, 자꾸 최적화 욕심이 나곤 합니다. “이렇게 하면 더 나을 것 같은데?” 하며 풀다보면 시간이 꽤 흐르기도 합니다.

취업을 위한 코딩 테스트 공부에서는 단순히 문제의 의도에 맞춰 통과하는 것을 목적으로 해야 할까요? 아니면 더 효율적이고 확장 가능한 방법을 고민해보는 것도 의미가 있을까요?

아래 코드는 큰돌님 코드보다 빠르게 동작하긴 하지만, 문제가 변형되어 예를 들어 N=10이 아니라 N=100이고, 필요한 평수가 5가 아니라 10평인 경우에도 가격을 미리 계산하고 정렬(sorting)하는 방식이 여전히 효율적일지는 잘 모르겠습니다.

문제를 풀 때 주어진 조건보다 더 확장 가능한 상황까지 신경을 쓰고 싶은데 아직 방법이 떠오르지는 않는 것 같습니다. 이런 고민은 점차 후반 주차 문제를 풀면서 자연스럽게 해결되는 문제일까요? 아니면 현재 단계에서도 고민해 보는 것이 바람직한 걸까요?

조언 주시면 정말 감사하겠습니다!

https://www.acmicpc.net/source/88073260

#include <bits/stdc++.h>

using namespace std;

struct Land {
  int price;
  int y;
  int x;
};

bool isValid(const Land& a, const Land& b) {
  return abs(a.x - b.x) + abs(a.y - b.y) >= 3;
}

int p[10][10];
int N;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> N;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> p[i][j];
    }
  }

  vector<Land> flowers;
  for (int i = 1; i < N - 1; i++) {
    for (int j = 1; j < N - 1; j++) {
      int price =
          p[i][j] + p[i - 1][j] + p[i + 1][j] + p[i][j - 1] + p[i][j + 1];
      flowers.push_back({price, i, j});
    }
  }

  sort(flowers.begin(), flowers.end(),
       [](const Land& a, const Land& b) { return a.price < b.price; });

  int minCost = INT_MAX;

  int flowerCount = flowers.size();
  for (int i = 0; i < flowerCount - 2; i++) {
    for (int j = i + 1; j < flowerCount - 1; j++) {
      if (!isValid(flowers[i], flowers[j]))
        continue;

      int currentCost = flowers[i].price + flowers[j].price;

      for (int k = j + 1; k < flowerCount; k++) {
        if ((currentCost + flowers[k].price) >= minCost)
          break;

        if (!isValid(flowers[i], flowers[k]) ||
            !isValid(flowers[j], flowers[k]))
          continue;

        minCost = currentCost + flowers[k].price;
      }
    }
  }

  cout << (minCost == INT_MAX ? -1 : minCost) << '\n';
  return 0;
}