본문 바로가기

전체 글

 (105)
[프로그래머스]다리를 지나는 트럭 처음에 무작정 풀려하다가 삽질만 한 거 같다. 결론적으로 큐를 이용해서 풀면 쉽게 풀 수 있는데 딱히 어려운 부분은 없다. #include #include #include #include using namespace std; int solution(int bridge_length, int weight, vector truck_weights) { int answer = 0; queue mQ; int seq = 0; int time = 1; int total_weights = 0; mQ.push({seq, time}); total_weights += truck_weights[seq++]; while(!mQ.empty()) { if(time - mQ.front().second + 1 >= bridge_leng..
[프로그래머스]멀쩡한 사각형 y, x축의 값이 정수가 나타날 때의 간격이 일정하다는 것 제외해야할 칸의 개수가 각각의 정수 사이의 y, x거리의 합 -1이란 것을 알면 문제를 해결할 수 있다. (단! 범위를 초과하여 ac를 못 받을 수 있으면 주의하자) using namespace std; long long solution(int w,int h) { long long answer = (long long)w * (long long)h; int div = w > h ? h : w; while(w % div != 0 || h % div != 0) { div--; } answer = answer - (div * (w / div + h / div - 1)); return answer; } Colored by Color Scripter cs
2186번: 문자판 시간초과 해결하는데 상당히 힘들었던 문제입니다. 백트래킹과 비슷한 방식을 사용하는데 DP방식과 섞는 느낌?으로 DFS를 구성하면 답을 구할 수 있습니다. #include #include #include typedef struct { int y, x; } dif; dif dir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; int visited[101][101][101] = { 0 }; std::string map[101]; std::string result; int row, col, term; int DFS(int y, int x, int idx) { if(visited[y][x][idx - 1] != -1) { return visited[y][x][idx - 1]; } v..
2133번: 타일 채우기 문제를 보고 자신감이 떨어져 다른 분이 작성한 답을 참고했다.... https://jaimemin.tistory.com/330 백준 2133번 타일 채우기 문제 링크입니다: https://www.acmicpc.net/problem/2133 타일링 문제가 상당히 흥미로웠기 때문에 백준 알고리즘 문제를 한번 풀어봤습니다. 알고스팟에서 익혔던 방법대로 풀었더니 쉽게 풀렸습니다! (http://ja.. jaimemin.tistory.com https://www.crocus.co.kr/688 [2133번] 타일 채우기 문제 출처 : https://www.acmicpc.net/problem/2133 알고리즘 분석 : 문제 해결에 필요한 사항 1. Dynamic Programming 2. 점화식 세우는 방법 상태 다..
2011번: 암호코드 현재 숫자와 이전숫자가 11 ~ 26일 경우 현재 숫자와 이전 숫자를 따로 봤을 때 가능한 이전까지의 방법 수와, 하나의 봤을 때 가능한 이전이전까지의 방법 수를 더해서 답을 구했다. 그리고! 10으로 나누어 떨어질 때 가능한 경우는 1이므로 적절한 예외처리가 필요하다. 첫째 자리가 0일 경우에도 코드 조합을 만들 수 없으므로 적절한 처리를 해주자. #include #include int main(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::string val; std::cin >> val; int dp[5001] = { 0 }; dp[0] = 1; dp[1] = dp[0]; int check = (val[0] - '0'..
[하노이 탑]재귀 재귀를 약간 알고 있는 정도였는데 하노이 탑 문제를 보고 상당히 당황했다. 그래서 잘 알고자 정보를 찾아봤는데 아래 사이트에서 재귀에 대해 조금 더 이해할 수 있었다. https://www.acmicpc.net/board/view/19958 글 읽기 - 하노이탑 재귀함수 쉽게 이해하는 방법 있나요? 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net
10844번: 쉬운 계단 수 dp문제다. 0, 9 는 퍼져나갈 수 있는 1과 8밖에 못받고 나머지는 자신의 수 -1, +1인 수의 개수를 받을 수 있다는 것을 이용했다. 처음에 0이 오면 안되기 때문에 마지막에서부터 연산을 진행해 최종적으로 1~9로 시작할 수 있는 계단 수를 더해서 답을 구한다. (아래의 식을 이용하면 sum이 아닌 dp만을 나누어 준다는 것에 주의! sum += dp[len-1][k] % 1000000000;) #include int main(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int len; std::cin >> len; long long dp[101][10] = { 0 }; for(int i = 0; i
10815번: 숫자 카드 카드의 개수가 많기 때문에 순차적으로 탐색한다면 시간초과가 난다. 이분 탐색을 이용해 시간복잡도를 줄이면 정답을 얻을 수 있다. #include #include int user1Card[500001] = { 0 }; int user1Count, user2Count; int search(int val, int front, int end) { int mid = (front + end) / 2; // std::cout

티스토리툴바