본문 바로가기

전체 글18

[BOJ] 1052 물병 C++ 문제이해 N개의 물병을 가지고 있는 상태에서 차있는 물병이 K개가 되도록 만드려고 한다. 재분배는 같은 양의 물이 들어있는 물병 두 개를 고르고 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. (상점에서 새로운 1리터 물병을 살 수 있다.) 즉, N으로 같은 양의 물이 들어 있는 물병을 합치면서 K개가 될 수 있는지 확인하고 된다면 상점에서 사야하는 물병의 최솟값을 구해야 하는 문제이다. 아이디어 구상 N, K = 3, 1 1 1 1 -> 2 1 -> 2 2 -> 4로 1개의 물병을 구매하면 된다. N, K = 13, 2 1 x 13 -> 2x6, 1 -> 4 4 4 1 -> 8 4 1 -> 8 4 4 -> 8 8 -> 16으로 3개의 물병을 구매하면 된다. 위와 같이 N은 2로 나누면.. 2023. 11. 13.
현대모비스 예선 - 주차시스템 문제 이해 n x m 형태의 배열이 주어지면 가장 점수가 높은 주차 구역의 점수를 출력하는 문제. 아이디어 구상 bfs를 nm번 돌면서 방문하지 않았으면서 1이 아닌 경우(주차되어 있지 않거나 장애인 주차 구역인 경우) bfs를 돌리도록 하면서 해당 x,y값을 벡터에 담아 주차구역의 점수를 구할 때 사용. 코드 #include #include #include using namespace std; #define MX 2005 int a[MX][MX], vis[MX][MX]; int n, m, res; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; vector v; int inRange(int x, int y){ return 0 > m; for(int .. 2023. 9. 7.
구름톤 챌린지 - 19일차 문제 이해 도시의 수 N, 도로의 수 M, 출발 도시 S, 도착 도시 E가 주어지고 M줄에 걸쳐 연결된 도시들의 번호가 주어진다. N까지 도시에서 i = 1 to N일 때 i번째 도시를 사용하지 않고 출발 도시에서 도착 도시까지 도착 여부를 구하는 문제. 아이디어 구상 첫번째 시도 벡터를 사용하여 BFS를 돌리면서 방문체크를 하면 될거라 추측했다. 결과 : SUCCESS 두번째 시도 위와 동일하지만 DFS로 돌려봤다. 결과 : FAIL 이유 : 3번째 예제에서 제대로 동작하지 않았다. 혹시 몰라서 벡터들을 정렬시키고 해봤지만 역시나 마찬가지. 조금 더 생각해보고 다시 풀어볼 예정. 코드 #pragma warning(disable:4996) #include #include #include #include .. 2023. 9. 7.
구름톤 챌린지 - 18일차 문제 이해 N x N 형태의 정사각형이 주어지고 M개의 반직선을 그린 뒤 교차하는 점의 개수를 세는 문제. 아이디어 구상 첫번째 시도 dx, dy 테크닉을 사용하여 범위 안에서 한쪽 방향으로 끝까지 체크하도록 시도했다. 결과 : FAIL 이유 : 단순하게 x,y를 찍어버리게 되면 길이가 1 x 1인 경우 예외적인 케이스가 발생하게 됨. 두번째 시도 가로와 세로를 나눠서 L, R일 때와 U, D를 각각 체크시킨 후 반복문을 돌면서 해당 위치에 있는 값을 곱해주면 해당 위치에 얼마만큼 교차해있는지 알 수 있을 것이라 추정. 결과 : SUCCESS 코드 #include #include using namespace std; #define MX 105 int n, m; long long a[MX][MX], b[M.. 2023. 9. 6.

티스토리툴바