전체 글102 [C] 2748: 피보나치 수 2 그냥 피보나치 수열을 만들면 된다. 다만 범위가 int형을 벗어나기 때문에 long long int를 사용해야한다는 것만 주의하면 쉽게 풀 수 있다!! #include int long long fibo[91]; int main(void) { int n; scanf("%d",&n); fibo[0]=0; fibo[1]=1; fibo[2]=1; for(int i=3;i 2023. 7. 30. [C] 10026: 적록색약 그 동안 너무 BFS로만 풀어서 오랜만에 DFS로 풀었다 사실 구역이 몇개인지 알아보는 문제들은 그래프를 다 순회하기만 되기 때문에 BFS를 쓰든 DFS를 쓰든 아무 상관이 없다. 하지만 그래프 내에서 최소로 도달하는 순서나 그래프 순회를 넓이 우선으로 해야하는 경우는 BFS를 써야한다. 사실 아직 많이 풀어보지는 못했지만 DFS로만 풀리는 문제는 보지 못해 헷갈린다면 그냥 BFS를 써야겠다. 그리고 정수를 한꺼번에 배열처럼 받을때 %1d를 사용하면 하나씩 값을 얻을 수 있는데 %1c는 그런게 없다. 항상 배열의 시작이 0인지 1인지 잘생각하면서 풀어야겠다는 생각이 들었다. 또 이 문제와 같이 그래프안의 원소의 값이 달라질때는 아예 clear()함수를 만들어 초기화 시켜주는게 더 깔끔한 것 같다. #in.. 2023. 7. 30. [C] 1149: RGB거리 전형적인 Dynamic Programming 문제인걸 알 수 있었는데 그 이유는 subproblem을 여러번 이용해야하기 때문에 이를 위해서 dp[]에 저장해서 이용해야했고 최솟값과 관련된 문제였기 때문이다. 이 문제는 i=1일때부터 하나하나씩 해보면 점화식을 구하는 것보다는 i=n일때부터 거꾸로 생각하는게 좀 더 떠올리는게 쉬웠던 것 같다. (2Xn 타일링2와 같이!) 그리고 빨강,초록,파랑 각각을 선택했을때 최선인 경우를 따로따로 저장하는 것이 각각 생각하지 않고 dp[i]일때 최선인 것을 저장하는 것보다 효율적이었는데 이는 똑같은 색깔을 두번 연속 선택하지 못한다면 그 다음에 최선인 경우를 빨리 찾기 위해서이다. #include int red[1001]; int green[1001]; int blu.. 2023. 7. 30. [C] 7576: 토마토 일단 BFS를 이용하여 초기의 있던 토마토마다 BFS 알고리즘을 이용하여 각 그래프의 점에서 언제가 토마토가 가장 빨리 익는지를 비교하여 배열에 저장하고 마지막에 최댓값을 구하는 방식으로 코드를 짰다. 그렇게 하기 위해 queue_day라는 배열을 생성하여 하루가 지날때마다 하루가 추가되도록 만들었고 새로운 초기 토마토로 BFS를 탐색할 때마다 공통으로 쓰이는 배열들을 초기화해줬다. 또 다 익게 만들 수 없는 경우가 다 익은 경우를 구별해서 구했다. 그래서 그 결과!! 테스트 케이스는 다 맞는데 시간초과가 나오게 됐다.. #include int arr[1001][1001]; int visit[1001][1001]; int queue[1001][2]; int queue_day[1001]; int x_coo.. 2023. 7. 30. 이전 1 ··· 14 15 16 17 18 19 20 ··· 26 다음