글 읽기 - 안녕하세요, 궁금한 게 있어서 질문 드립니다.

lgs5751 4년 전 0

1 4

antatica

위 테스트케이스에 대해 틀린 부분을 찾다가 30번째줄에서 k가 -1이고 dq.size()가 0일때 첫번째 if문이 실행되어 오답처리된 것을 확인할 수 있었습니다.

아무리 생각해봐도 k=-1, dq.size()=0일때 해당 조건문이 왜 실행되는지 모르겠습니다. 고수님들 답변 부탁드립니다!

#include <stdio.h>
#include <memory.h>
#include <deque>
using namespace std;

char word[51][20];
int selected[26], result, n, k;
deque<char> dq, dq2;

void dfs(int, int);

int main()
{
	scanf("%d %d", &n, &k);
	k = k - 5;
	selected['a' - 'a'] = 1, selected['n' - 'a'] = 1, selected['t' - 'a'] = 1, selected['i' - 'a'] = 1, selected['c' - 'a'] = 1;
	for (int i = 0; i < n; i++)
	{
		scanf("%s", word[i]);
		for (int j = 0; word[i][j] != '\0'; j++)
		{
			if (selected[word[i][j] - 'a'] == 0)
			{
				dq.push_back(word[i][j]);
				selected[word[i][j] - 'a'] = 1;
			}
		}
	}

	if (k >= dq.size()) printf("%d\n", n);
	else if (k < 0) printf("0\n");
	else
	{
		memset(selected, 0, sizeof(selected));
		selected['a' - 'a'] = 1, selected['n' - 'a'] = 1, selected['t' - 'a'] = 1, selected['i' - 'a'] = 1, selected['c' - 'a'] = 1;
		dfs(0, 0);
		printf("%d\n", result);
	}

	return 0;
}

void dfs(int idx, int cnt)
{
	if (cnt == k)
	{
		int ret = 0;

		for (int i = 0; i < n; i++)
		{
			bool check = true;
			for (int j = 4; word[i][j] != '\0'; j++)
			{
				if (selected[word[i][j] - 'a'] == 0) {
					check = false;
					break;
				}
			}
			if (check == true) ret++;
		}
		if (ret > result) result = ret;

		return;
	}
	if (idx >= dq.size()) return;

	selected[dq.at(idx) - 'a'] = 1;
	dfs(idx + 1, cnt+1);
	selected[dq.at(idx) - 'a'] = 0;
	dfs(idx + 1, cnt);
}

shg9411 4년 전 0

c++에 대해서 잘 알지 못하지만 초기화가 되지 않아서 그런 것 같습니다.

선언만런 되어있어서 그런 것 같아 따로 사이즈를 변수에 저장해주고 그 변수로 비교했더니 통과되네요

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

문제

문제

출처

ICPC

안녕하세요, 궁금한 게 있어서 질문 드립니다.

lgs5751 4년 전 0

shg9411 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말