글 읽기 - 3078 - 좋은 친구 행님덜... 도와주세요... ㅠㅠㅠ

gfdhq 5년 전 1

O(N^2) 로 하면 시간초과가 떠서 조금이나마 연산을 적게 하고자 코드를 수정했습니다.

그러나, 현재 코드는 '틀렸습니다' 가 계속 발생합니다.

빅오 표기법으로 현재 코드가 어떻게 되는지는 잘 모르겠습니다...

해당 코드를 이해하기 어려우실 수도 있습니다.

그래서 가능한 주석을 최대한 달았습니다.

제가 짠 로직이 잘못되었는지... 혹은 코드가 잘못되었는지 조언 좀 부탁드립니다.

채점번호 : 11274941

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#define STRLEN_MAX 21

//해당 문제에서는 v[x][y]('철수') 기준으로 크기 k만큼 왼쪽 오른쪽으로 좋은 친구의 쌍을 구하는 것이기 때문에
//v[x][y+1]는 v[x][y]와 좋은 친구일 경우 
//v[x][y] 기준으로 오른쪽의 친구만 구한다면
//v[x][y+1]은 자신의 왼쪽 친구들이 좋은 친구인지 아닌지 몰라도 상관이 없다.
//그러므로, 오른쪽으로만 계속해서 친구를 구해나간다.


using namespace std;

int n, k;
vector<vector<int>> v;
int result = 0;

void function()
{
	//벡터 크기 만큼 for문.
	for (int x = 0; x < v.size(); x++){
		int front = 0;

		//이름의 길이가 같은 친구들 모두 한번씩 체크.
		for (int y = 0; y < v[x].size(); y++){
			
			//front와 y는 비교를 해야하기 때문에 y증가.
			if (front == y){
				continue;
			}

			//y지점과 front 지점 비교시 k보다 크다면...
			//v[x][y-1] - v[x][front] <= k
			//가 성립.
			//y-1-front == front의 좋은친구 크기 이므로 result += y-1-front
			while (v[x][y] - v[x][front] > k){
				result += y - 1 - front;
				front++;
			}

			//for문 마지막일 경우 아직 확인하지 않은 친구들은 모두 좋은 친구
			//왜냐 하면, 위의 while(v[x][y] - v[x][front] > k)의 while문으로 들어가지 않았기 때문에 남은 친구들은 모두 좋은 친구들이다.
			//front 와 v[x].size()-1 사이에 있는 값들은 k보다 작거나 같다.
			if (y == v[x].size() - 1){
				while (front != v[x].size() - 1){
					result += y - front;
					front++;
				}
			}
		}
	}
}

int main(void)
{
	v.resize(STRLEN_MAX);

	cin >> n >> k;

	for (int i = 0; i < n; i++){
		string input_data;
		cin >> input_data;
		v[input_data.size()].push_back(i); //v[문자열의 길이]에 해당 인덱스 저장.
	}

	function();
	
	cout << result << endl;

	return 0;
}

cgiosy 5년 전 3

답이 최대 n(n-1)/2로 int 범위를 초과하기 때문에, long long을 사용해야 합니다.

gfdhq 5년 전 0

답변 너무나 고맙습니다.. ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ 바로 결과가 나오네요

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

문제

문제

출처

ICPC

3078 - 좋은 친구 행님덜... 도와주세요... ㅠㅠㅠ

gfdhq 5년 전 1

cgiosy 5년 전 3

gfdhq 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말