[네번째 문제] 백준 / 1058 : 친구
solved.ac 기준으로 실버1문제를 푸는 중이고 ,
등급이 실버1이 되면 골드5문제로 넘어갈 예정이다.
( 실버1이 되지 않더라도 배움이 충분하다고 생각 되면 넘어간다)
현재 : 실버5
# include <iostream>
using namespace std;
char arrFriend[51][51];
// 2친구수를 구하려면 , 직접 친구이거나, 같이 아는 사람이 존재해야한다
//N Y N N -- > A는 B와는 친구지만 C , D와는 직접 친구가 아니다. 그러나 C ,A와 친구인 B가 있으므로 2친구수 +1 DA와친구인 B도 있으므로 2친구수 +2
//Y N N N
//N N N Y
//N N Y N
// 50명 기준으로
// 연산은 50X50X50
int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arrFriend[i][j];
}
}
int maxi = 0;
for (int i = 0; i < N; i++) {
int fcnt = 0;
for (int j = 0; j < N; j++) {
if(arrFriend[i][j] == 'Y') fcnt += 1; // 직접친구
else {
for (int k = 0; k < N; k++) {
if (arrFriend[k][j] == 'Y' && arrFriend[k][i] == 'Y' ) {
fcnt += 1; // 다른친구와 나를 동시에 아는사람이 존재
break;
}
}
}
}
if (fcnt > maxi) maxi = fcnt;
}
if (maxi == 0) {
cout << maxi;
}
else cout << maxi -1 ;
return 0;
}
문제 자체는 직관적이었다.
삼중 for문의 경우 아름답지는 않지만 연산횟수가
50x50x50 = 125000회였기 때문에 지난번의 교훈을 벗삼아 쉽게 풀기로 했다.
여기서 치명적인 실수를 하게 되는데, 위와 같이 코드를 짜게 되면 본인 역시 2-친구로 인식하게 되어버려서 코드를 수정하기보다는 -1을 빼줘서 구하기로 했다.
그러나 테스트 케이스
2
NN
NN
의 경우 maxi 자체가 0이기 때문에 -1을 하면 안된다.
따라서 0인 경우를 else로 다시 처리해 줬지만,
if (i !=j && arrFriend[k][j] == 'Y' && arrFriend[k][i] == 'Y' )
위의 조건을 이렇게 바꿔주면 깔끔하게 해결 할 수 있다.
Author And Source
이 문제에 관하여([네번째 문제] 백준 / 1058 : 친구), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@plackyou123/네번째-문제-백준-1058-친구저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)