소프티어

시간초과 해결한 방법

저의 경우 dfs를 사용해서 k == 3일 때 각각의 값 중에 최대인 값을 계속해서 갱신해주는 방법을 썻습니다. 하지만 이럴필요 없고 k==2까지만 돌리면 됩니다. 왜냐하면 k == 2일때 부터는 굳이 dfs가 필요하지 않습니다. 어차피 k==2일 때는 지울수 있는 차 색깔의 최대값만 구하면 되기때문입니다. (k==3)일 때 종료되고 각각의 경우의 수가 더 이상 필요 없기 때문.... 그래서 k==2일 때 2중 for문으로 계속 dfs를 돌려줄 필요없고 바로 k == 2인 상황들에서 차 색깔의 최대값을 찾은 뒤에 바로 답을 구하시면 됩니다. 이 렇게 했더니 1.082초에서 0.9초로 통과가 됐습니다 흑흑...

garage game 테스트케이스 하나가 계속 안됩니다.... 고수님들 도와주세요

도와주세요...고수님들 도저히 모르겟어요... #include #include #include #include #include #include #include using namespace std; int n; int map[45][15]; int result = 0; int dy[] = { 0,0,-1,1 }; int dx[] = { 1,-1,0,0 }; void dfs(int cnt, int score) { if (cnt == 3) { result = max(result, score); //cout << "Done!!!!!!!!!!" << endl; return; } bool visited[15][15] = { false, }; int dup[45][15] = { 0 }; memcpy(dup, map, sizeof(map)); for (int i = 2 * n; i < 3 * n; i++) { for (int j = 0; j < n; j++) { int num = 1;...

[garage game] 어떤 부분에서 더 최적화 해야 할까요... 며칠째 고민 중입니다 고수님들 도와주세요

보시기 편하게 문제 링크 입니다 https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=540 먼저 저는 java로 풀었습니다 최적화를 위해서 여러가지 생각을 해 봤는데요... 1. 2차원 배열 말고 linked list 배열을 사용해서 넣고 빼기 쉽게 했습니다. (ArrayList도 해봤는데 시간초과..) 2. dfs를 쓸 때 배열을 copy하지 않고 필요한 부분만 뺐다 넣었다 했습니다. 3. 한 라운드에서 얻을 수 있는 최대값을 구해놓고(N*N*2) 최대로 더하는 경우에도 Max보다 작다면 그 경우는 실행하지 않도록 했습니다. 4. 삭제되는 블럭들의 위치 최대, 최소값을 minX, minY, maxX, maxY 에 넣어놓고 사용해서 반복문의 횟수를 줄였습니다. 5. 3번째 단계에서는 블럭 삭제하는 연산을 하지 않고 세기만 했습니다 + 만약 최고 점수(N*N*2*3 이라면 아예 끝내도록 했습니다) 이 외에도 어떤 걸 더 해야 ...

Garage Game 반례를 찾고싶습니다 고수님들 도와주세요

아래 코드로 fail 7개 뜨네요 ㅠㅠ 고수님들의 도움 기다립니다,, #include #include #include #include #include using namespace std; int N; int new_block[45][15] = {0, }; int visit[45][15] = {0, }; int answer = 0; int real_answer = 0; stack answer_stack; bool compare(pair p1, pair p2){ if (p1.second == p2.second) { return p1.first < p2.first; } return p1.second < p2.second; } int dfs(int x, int y, int ref_val, vector > &block_vectors) { if(x<2*N || x>=3*N || y<=-1 || y>=N) return false; if((!visit[x][y]) && (new_blo...

Garage game 로직 문의..

아래처럼 단순 제거 후 내려가는 로직밖에 안 떠오르는데 블록의 색상이 모두 다른 경우에, N=8부터 시간 초과가 나네요 더 최적화할 부분이나 간단히라도 로직 힌트 부탁드립니다..! import sys def beatify(txt,ti): print(txt,ti) for y in range(len(arr[ti])-1,-1,-1): print(arr[ti][y]) def cpy(ti,r_arr): arr[ti]=[[0 for c in range(N)] for r in range((4-ti)*N)] # arr[ti]=[[0 for c in range(N)] for r in range(3*N)] visited[ti]=[[False for c in range(N)] for r in range(N)] for x in range(N): yc=0 for y in range((4-t...

garage game 반례좀 찾아주세요

안녕하세요 b type TC에서 실패하는데, 고수분들 반례 좀 부탁드립니다. 코드는 삭제합니다

Garage game 반례 부탁드립니다.

안녕하세요. 예시 입력들이 통과해서 제출했는데 테스트 케이스 중 절반 정도 오답이 나왔네요. 반례 케이스가 어떤게 있을까요?? import sys def getColor(square): square2lists = [] for r in range(N): for c in range(N): square2lists.append([square[r][c], [r, c]]) results = set() for square2list in square2lists: cur_r = square2list[1][0] cur_c = square2list[1][1] shouldIpass = 0 for result in results: if (cur_r, cur_c) in result[1]: should...