2-S dp 배열을 좀 더 이용해보려고 코드를 바꿔봤는데 틀렸습니다가 나오네요
아래는 맞는 코드입니다.
http://boj.kr/1b13bda362154df9b5be8a26cad57c96
이 코드를 개선해보려고 아래와 같이 코드를 짜보니 틀렸습니다가 나오네요.
http://boj.kr/a6cbb7ca3b214df386ebb96214bc2785
dp를 아직 잘 모르는데 선생님의 풀이를 보고 조금 더 횟수를 줄일 수 있지 않을까 해서 한번 바꿔봤는데요. 맞왜틀에 빠졌습니다... 도저히 혼자서는 이유를 찾을 수 없어서 질문드립니다!
답변 1
2
안녕하세요 상민님 ㅎㅎ
지금 보시면
for(int there : arr[here]) {
if(visited[there]) continue;
table[there] = dfs(there);
cnt += table[there];
}해당 노드로 부터 뻗어나가는 노드의 table에 담으신 거잖아요.
아마 그렇게 해서 dfs를 줄이는 방법을 생각하신 거 같은데요.
생각은 너무나도 좋습니다. ㅎㅎ
다만
2 -> 1 -> 3 -> 4 -> 1
이렇게 되었을 때
1부터시작하게 되면.
table 1 : 3
table 3 : 2
table 4 : 1
이렇게 되겠죠?
근데 사실은 이게 정답이죠.
table 1 : 3
table 3 : 3
table 4 : 3
이러한 반례 때문에 틀린 것 같습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
6-H 체점 관련 질문
0
15
1
채점서버 연결 관련 질문입니다
0
35
1
삼성 s직군
0
39
1
삼성 코테 없어짐
0
89
1
코딩살구클럽 가입부탁드립니다
0
43
2
코딩살구클럽 가입 요청 확인부탁드립니다
0
36
2
5-S 테스트 케이스 질문
0
37
2
코살 문제풀이 환경
0
54
2
2 - T 오큰수 문제가 있는 것 같습니다.
0
46
1
추천 추가문제들
0
44
2
프로그래머스 코테 환경 관련해서 질문드립니다.
0
50
2
해당 문제에 대한 채점이 코딩살구클럽에서 올바르게 처리되지 않습니다.
0
44
2
균형 이진 트리 설명 시 높이 숫자
0
34
2
4-H 질문드립니다.
0
38
2
1-K 질문드립니다.
0
44
2
대기업 인적성 시험 질문
0
44
2
4-C 질문드립니다
0
45
2
[수학숙제 / BOJ 2870] 채점 서버 오작동
0
41
1
코테 준비 질문
0
59
1
살구클럽가입 요청드려요
0
44
2
1-I 문제 질문
0
48
2
코딩살구클럽 가입
0
62
2
AI 코딩 도구 사용 시 학습 방법 조언
0
58
2
코딩살구클럽 오류
0
67
2