본문 바로가기

백준 문제풀이117

[백준][스위핑] 2170 선 긋기 c++구현 목차https://www.acmicpc.net/problem/2170문제 문제 구현 아이디어두 점의 범위가 억이 넘어가므로 일단 공간 복잡도상으로 배열은 사용하지 못한다는 것을 알 수 있다.따라서 갱신을 하며 누적해주는 식으로 풀었다.  코드 구현#include #include #include#include#include typedef long long ll;using namespace std;vector>v;ll N, x, y;ll total = 0;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 0; i > x >> y; v.push_back({ .. 2024. 8. 24.
[백준][이분탐색] 2632 피자판매 c++구현 목차https://www.acmicpc.net/problem/2632문제 문제 구현 방향연속된 값을 더하는 것이므로 일단 누적합이 생각났다.경우의 수가 매우 많으므로 각각의 경우를 구한뒤 합치는게 효율적이라고 생각했다. 문제 풀이 시 아이디어 1. 원형 배열 직선 배열로 만들기22172 아래와 같이 배열을 한번 더 합치면 원형 배열 구간합 탐색이 가능하다.2217222172 단 시작점이 초기 배열 사이즈-1 인덱스에 오면 탐색을 멈추어야 중복을 막을 수 있다.사이즈가 초기 배열 사이즈만큼일때는 한번 탐색하고 중단해야한다.  2. 각 경우 곱해서 구하기만들어 질 수 있는 각각의 경우를 구해 준 뒤 곱해서 더해준다. for (int i = 0; i  코드 구현#include #include #inclu.. 2024. 8. 19.
[백준][구현] 15685 드래곤 커브 c++구현 목차https://www.acmicpc.net/problem/15685문제 문제 구현 방향각 드래곤의 방향을 구한뒤 맵과 벡터에 좌표를 넣고 탐색하는 식으로 구현했다. 문제 아이디어 1. 드래곤의 방향을 넣고 좌표 구하기드래곤의 움직임은 결국 방향벡터의 size만큼 세대별로 거꾸로 탐색해 방향벡터+1을 더한 값을 넣어주면 된다.void dragonMoving() { vector direct; for (int i = 0; i = 0; j--) { direct.push_back((direct[j] + 1) % 4); } } int sx = v[i].x; int sy = v[i].y; if.. 2024. 8. 17.
[백준][구현][백트래킹] 17825 주사위 윷놀이 c++구현 목차https://www.acmicpc.net/problem/17825문제 문제 구현 방향인접리스트에 저장해놓고 말 4개를 백트래킹하는 방식으로 구현했다.말 4개를 10번 움직이는 것이므로 4^10이라는 탐색 시간은 충분히 구현할 수 있다.   문제 구현 시 주의점말이 모일 때 예외처리를 매우 잘해주어야 한다. (25, 30, 35, 40)도착지에 가면 말은 바로 멈춘다는 사실도 주의해야 한다.또한 도착지에는 말이 여러개 갈 수 있다는 사실을 주의해야 한다.  코드 구현#include #include using namespace std;vector v[10] = { {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38,.. 2024. 8. 17.
728x90

티스토리툴바