글 읽기 - 경사로 문제 - 75%에서 틀렸다고 뜹니다..

kke0949 6년 전 1

코드동작은

1. row와 col 라인들이 문제 없는지 한 라인씩 확인한다 - O(2N)

2. 현재 값이 앞의 값과 다른 경우 경사로를 지을 수 있는지 계산한다

3. L의 길이만큼 비교하여 모두 같은 숫자를 가지고 있다면 경사로를 만들 수 있다.

-> 만일 연산 중 변수 nowCol이 범위를 벗어나거나, 그 자리에 경사로가 이미 있거나, 같지 않은 숫자가 있는 경우 경사로를 만들수 없다.

-> 각 라인마다 Slope라는 벡터를 이용하여 경사로가 제작될때마다 true를 넣어줌으로써 그 자리에 경사로가 있는지 확인할 수 있게 한다.

4. 현재 값이 앞의 값보다 작은 경우 현재값에서부터 L만큼 경사로를 제작할 수 있는지 확인한다.

5. 현재 값이 앞의 값보다 큰 경우 앞의 값부터 뒤로 L만큼 경사로를 제작할 수 있는지 확인한다.

-> 4번의 경우 경사로가 제작가능할 시 그 부분을 다시 비교하지 않기 위해 row/col을 L - 1만큼 이동한다

6. 경사로 제작에 문제가 없거나 경사로를 만들 필요가 없는 라인이라면 ans++을 한다.

7. ans를 출력한다.

이런식으로 생각해서 코드를 짰씁니다...

나올 수 있을만한 반례들을 몇개 생각해서 넣어봐도 답이 나와서 어떤 반례가 있는지를 모르겠습니다ㅠㅠㅠ

코드에서 어떤 반례가 있을까요??

코드가 깨끗하지가 않아서 죄송합니다 ㅠㅠ

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

int arr[101][101];

int main()
{
	int n, L;
	cin >> n >> L;

	for (int row = 0; row < n; row++)
	{
		for (int col = 0; col < n; col++)
			cin >> arr[row][col];
	}
	
	int ans = 0;

	// 1. row와 col 라인들이 문제 없는지 한 라인씩 확인한다 - O(2N) 
	// 2. 현재 값이 앞의 값과 다른 경우 경사로를 지을 수 있는지 계산한다
	// 3. L의 길이만큼 비교하여 모두 같은 숫자를 가지고 있다면 경사로를 만들 수 있다.
	//  -> 만일 연산 중 변수 nowCol이 범위를 벗어나거나, 그 자리에 경사로가 이미 있거나, 같지 않은 숫자가 있는 경우 경사로를 만들수 없다.
	//  -> 각 라인마다 Slope라는 벡터를 이용하여 경사로가 제작될때마다 true를 넣어줌으로써 그 자리에 경사로가 있는지 확인할 수 있게 한다. 
	//
	// 4. 현재 값이 앞의 값보다 작은 경우 현재값에서부터 L만큼 경사로를 제작할 수 있는지 확인한다.
	// 5. 현재 값이 앞의 값보다 큰 경우 앞의 값부터 뒤로 L만큼 경사로를 제작할 수 있는지 확인한다.
	//  -> 4번의 경우 경사로가 제작가능할 시 그 부분을 다시 비교하지 않기 위해 row/col을 L - 1만큼 이동한다
	//
	// 6. 경사로 제작에 문제가 없거나 경사로를 만들 필요가 없는 라인이라면 ans++을 한다.
	// 7. ans를 출력한다.

	// row쪽 먼저
	for (int row = 0; row < n; row++)
	{
		bool isSlopePossible = true;
		vector<bool> Slope(n, false);

		for (int col = 1; col < n; col++)
		{
			// 현재 값이 앞의 값보다 더 작은 경우!
			if (arr[row][col - 1] > arr[row][col])
			{
				// L의 길이만큼 비교
				for (int nowCol = col; nowCol < col + L; nowCol++)
				{
					// nowCol이 범위를 벗어나거나, 경사로가 이미 있거나, 처음값과 같지 않음 = L만큼의 경사로를 만들수없음
					if (nowCol >= n || nowCol < 0 || Slope[nowCol] == true || arr[row][col] != arr[row][nowCol])
					{
						isSlopePossible = false;
						break;
					}
				}

				if (isSlopePossible == false)	break;
				
				// 경사로가 지어졌기 때문에 다시 쓸수 없게 true 표시를 한다
				for (int nowCol = col; nowCol < col + L; nowCol++)
					Slope[nowCol] = true;

				col += L - 1;

			}
			// 현재 값이 앞의 값보다 더 큰 경우!
			else if (arr[row][col - 1] < arr[row][col])
			{
				// L의 길이만큼 비교하되! 거꾸로 확인한다!
				for (int nowCol = col - 1; nowCol >= col - L; nowCol--)
				{
					if (nowCol >= n || nowCol < 0 || Slope[nowCol] == true || arr[row][col - 1] != arr[row][nowCol])
					{
						isSlopePossible = false;
						break;
					}
				}

				if (isSlopePossible == false)	break;

				// 경사로가 지어졌기 때문에 다시 쓸수 없게 true 표시를 한다
				for (int nowCol = col - 1; nowCol >= col - L; nowCol--)
					Slope[nowCol] = true;

			}
		}

		if (isSlopePossible == true)	ans++;
	}


	// 다음 col쪽 계산
	for (int col = 0; col < n; col++)
	{
		bool isSlopePossible = true;
		vector<bool> Slope(n, false);

		for (int row = 1; row < n; row++)
		{
			// 현재 값이 더 작은 경우!
			if (arr[row - 1][col] > arr[row][col])
			{
				// L의 길이만큼 비교
				for (int nowRow = row; nowRow < row + L; nowRow++)
				{
					if (nowRow >= n || nowRow < 0 || Slope[nowRow] == true || arr[row][col] != arr[nowRow][col])
					{
						isSlopePossible = false;
						break;
					}
				}

				if (isSlopePossible == false)	break;

				// 경사로가 지어졌기 때문에 다시 쓸수 없게 true 표시를 한다
				for (int nowRow = row; nowRow < row + L; nowRow++)
					Slope[nowRow] = true;
				
				row += L - 1;

			}
			// 현재 값이 더 큰 경우! 
			else if (arr[row - 1][col] < arr[row][col])
			{
				// L의 길이만큼 비교하되! 거꾸로 확인한다!
				for (int nowRow = row - 1; nowRow >= row - L; nowRow--)
				{
					if (nowRow >= n || nowRow < 0 || Slope[nowRow] == true || arr[row - 1][col] != arr[nowRow][col])
					{
						isSlopePossible = false;
						break;
					}
				}

				if (isSlopePossible == false)	break;

				// 경사로가 지어졌기 때문에 다시 쓸수 없게 true 표시를 한다
				for (int nowRow = row - 1; nowRow >= row - L; nowRow--)
					Slope[nowRow] = true;

			}
		}		
		
		if (isSlopePossible == true)	ans++;
	}

	cout << ans << endl;
}

kke0949 6년 전 3

아 이제 보니 경사 차이가 2 이상일때는 경사로를 아예 만들수 없는데

그 경우의 예외처리를 하지 않았습니다 ㅠㅠ

그 조건을 넣어주니까 맞았다고 뜨네요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

경사로 문제 - 75%에서 틀렸다고 뜹니다..

kke0949 6년 전 1

kke0949 6년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말