inflearn logo
강의

Course

Instructor

Coding Test Practice Test (with C++): For Large Companies

3. Solution to the problem of drawing a square (Dynamic: DP)

코드 한번 봐주시면 감사하겠습니다!

175

ismy123

8 asked

0

제가 적은 코드가 시간 초과가 떠서 강사님께서 올려주신 코드로 채점해봤는데도 시간 초과가 나옵니다...

한번 봐주시면 감사하겠습니다~!

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<vector<int> > dy(n, vector<int>(m, 0));
	vector<string> board;
	vector<int> answer(min(n, m) + 2);

	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		board.push_back(tmp);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == '0') continue;
			int a = 0, b = 0, c = 0;
			if (i - 1 >= 0) a = dy[i - 1][j];
			if (j - 1 >= 0) b = dy[i][j - 1];
			if (i - 1 >= 0 && j - 1 >= 0) c = dy[i - 1][j - 1];
			int m = min(a, min(b, c));
			dy[i][j] = m + 1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 1; k <= dy[i][j]; k++) {
				answer[k]++;
			}
		}
	}
	for (int i = 1; ; i++) {
		if (answer[i] == 0) break;
		cout << i << " " << answer[i] << endl;
	}
	return 0;
}

어디가 문제인지 잘 모르겠습니다 :(

C++ 코테 준비 같이 해요!

Answer 1

0

codingcamp

안녕하세요^^

제가 보기에는 문제가 없는 코드인것 같습니다. 채점서버가 간혹 그럴수 있습니다.

조합을 구할때 algorithm 함수 next_permutation 사용 가능 여부

0

457

1

최악의 경우 연산 질문이 있습니다.

0

411

1

로컬 환경과 다르게 오답이라고 나와서 문의 드립니다.

0

302

1

6강 3번 정사각형 그리키 코드 질문 드립니다.

0

242

1

1-5 효율적인 공부 dy를 시간(N)으로 하는 풀이 질문

0

320

1

반복수와 시간초 계산을 어떻게 하나요??

0

333

1

왜 DP로 풀어야하는지 궁금합니다

0

242

1

선생님 안녕하세요. 다른 풀이에 대한 질문이 있습니다.

0

223

1

문제 해결방법에 대한 질문이 있습니다.

0

245

0

바둑대회 코딩 질문

0

270

1

6분 11초에서 dis [0][][]3차원 격자판이있는데요. 격자판안에 숫자는 문제에 없던데 어떻게 구해지는건가요?

0

200

0

실전모의고사 5회 1번 패턴찾기 질문있습니다.

0

220

1

전역변수관련 질문입니다.

0

255

1

5-1 패턴찾기 문제 질문드립니다.

0

218

1

오렌지 나무 문제 질문드립니다

0

310

1

코드 한번 봐주시면 감사하겠습니다!

0

234

1

코드 한번 봐주시면 감사하겠습니다!

0

198

1

시작점의 ch

0

204

1

vector에서 질문이 있습니다~!

0

235

1

그대로 따라했는데 시간 초과가 나왔습니다

0

161

1

2회 모의고사 4번 숲속의 기사 코드 질문이 있습니다.

0

288

1

질문있습니다.

0

209

1

이렇게 풀면 반례가 어떻게되나요?

0

245

1

1회 1번 공통 문자열 문제 설명 보충하시면 더 좋을 것 같습니다!

0

221

1