C++/백준 문제풀이 (3) 썸네일형 리스트형 2167번 2차원 배열의 합 https://www.acmicpc.net/problem/2167 이 문제는 3중 for문으로 풀어도 정답이 인정된다. 그러나 많은 사람들이 dp로 문제를 풀었고 3중 포문으로 풀었으니 나 또한 dp로 풀어보려고 한다. 아래는 3중 포문으로 푼 코드인데 실제로 400ms 정도 걸려 오랜 시간이 걸린다. #include using namespace std; int num[301][301]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int y, x; cin >> y >> x; for(int i=1; i num[i][j]; } } int k, startY, startX, endY, endX, sum = 0; cin >> k; for(int i=0; .. 1676번: 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제를 너무 간단하게 생각했다. 팩토리얼 구한 뒤 0의 갯수를 체크하려 하였는데 당연히 500!같이 큰 수의 경우 시간초과가 났다. 그래서 규칙을 찾아보았다. 접근은 좋았으니 5의 갯수를 세어야 하는데 5로 나눈 몫을 구했다.. 25와 125같은 경우만 처리하면 되는줄 알았는데 50, 75, 100, 등등 너무 많은 수가 있었기에 이것 또한 불가능하였다. 결국 문제의 핵심은 2를 몇 번 곱하였고 5를 몇 번 곱하였는지를 계산하여 10을 곱한 횟수를 통해 0의 갯수를 세는 것이다. 하.. 11866번: 요세푸스 문제0 먼저 원형 큐를 구현한 뒤 그 안에서 첫번째 자리를 삭제하는 경우와 이 외의 경우로 나누어 풀이를 작성하였다. 이 문제를 풀기 전에 큐에 대해 공부한 뒤, 단방향 연결리스트로 큐를 구현이 가능하다면, 원형 큐를 구현한 뒤 접근하면 매우 쉽게 풀린다. 놓친 점 : 첫번째 수를 빼는 경우를 고려하지 않아서 오류가 났었다. 그리하여 경우를 두가지로 나누어 삭제를 진행하였다. 또한 삭제의 경우 head = head->next; 와 같이 작성한 적이 많은데 이 경우 메모리 누수가 발생하고 n이 커지면 무수한 손실이 발생하여 delete를 사용하여 꼭 해제해주어야 한다. #include using namespace std; struct Node{ int num; Node *next; }; Node *tail, *h.. 이전 1 다음
