본문 바로가기

전체 글

BOJ)12841 정보대 등산 문제: icpc.me/12841 왼쪽 1번 지점에서 오른쪽 n번 지점까지 가는 최단 거리를 구하는데 이 때 횡단보도는 한번 밖에 못 건넌다는 전제가 있다. N개의 횡단보도를 건너는 케이스를 전부 확인을 해줘야 하는데 N이 10만이나 되기 때문에 모든 케이스를 직접 더해줄 경우 TLE를 받을 수 있다. 하지만 Partial sum을 이용한다면 왼쪽 오른쪽길의 횡단보도 기준으로 위 아래는 쉽게 구할 수 있다. 주의 할 점은 10만개의 횡단보도에 거리가 10만 까지 들어올 수 있으므로 long long을 사용해줘야 한다. 12345678910111213141516171819202122232425262728293031#include #include #define INF 999999999987654321using.. 더보기
BOJ)1865 웜홀 문제: icpc.me/1865 방향 그래프에서 시간이 거꾸로 간다는 개념이 나온다면 우선 벨만-포드를 생각해 볼 수 있다. 이때 주의 할 점은 도로는 방향이 없으므로 양 방향에 연결을 해줘야 한다. 문제에서 질문은 출발을 하였을 때 보다 시간이 되돌아 가 있는 경우가 있는지 확인하는 것인데 이것은 벨만-포드에서 음수 사이클 존재 여부를 확인하는 것과 동치다. 따라서 벨만-포드를 구현 한 뒤 음수 사이클 존재 여부에 따라 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include #define INF 987654321using namespace std;in.. 더보기
BOJ)11999 Milk Pails 문제: icpc.me/11999 X,Y,M이 주어졌을 때 X와 Y를 이용하여 M을 넘치지 않도록 최대한 얼마나 채울 수 있는지 구하는 문제이다. X,Y,M이 전부 1000이하이기 때문에 이터레이터를 1000번씩 돌려주면 되는 쉬운 문제다.O(N^2) 1234567891011121314151617#include #include using namespace std;int x, y, m, r;int main() { freopen("input.txt", "r", stdin); scanf("%d%d%d", &x, &y, &m); for (int i = 0; i 더보기

티스토리툴바