체뚱로그

풀이 시간: 3h57m12s90시간 복잡도: O(3^16)공간 복잡도: O(1)문제 입력첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.출력상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.문제 풀이우선 내 초기 문제 풀이는 이러하다. (오류)상어는 현재 방향의 물고기가 있는 모든 칸을 이동할 수 있다는 점에 있어서, dfs 백트래킹을 사용해야겠다고 생각했다.// 물고기 구조체 { 위치(x, y), 방향, 생존 여부 }struct ..

풀이 시간: 46m30s00시간 복잡도: O(N + MlogM + MlogN) // 입력 + 정렬 + 부모노드찾기공간 복잡도: O(N+M)참고 자료: https://medium.com/@lifthus531/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C%EC%99%80-%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC-63053849b989문제입력입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 줄에 u v d가 주어지며 u학교와..

풀이 시간: 35m34s75(초기 코드) + 14m(시간 초과 수정)시간 복잡도: O(N*M^4)공간 복잡도: O(N+M)문제BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.- A는 B와 친구다.- B는 C와 친구다.- C는 D와 친구다.- D는 E와 친구다.위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤..

풀이 시간: 1h23m18s29 + 1h20m44s32 + 42m34s25시간 복잡도: O(NMH) // H: 집의 개수공간 복잡도: O(N^2)참고 자료: https://yabmoons.tistory.com/50문제입력첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다. 둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다. 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.출력첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.문제 풀이초기 고민..

풀이 시간: 2h12m17s71시간 복잡도: O(N^2*L)공간 복잡도: O(N^2)문제입력첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.출력첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.문제 풀이전체 코드#include #include #include using namespace std;int N, L, ans = 0;vector cnt1, cnt2;int arr1[101][101] = { 0, };int arr2[101][101] = { 0, };vector isRoad(int arr[][101]) { vector cnt(N, true); // 각각의 길을 지나갈 수 있는..

풀이 시간: 2h30m33s56(문제풀이) + 2h13m41s24(틀린 부분 찾기)시간 복잡도: O(N^2)공간 복잡도: O(N^2)문제입력첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.출력격자의 밖으로 나간 모래의 양을 출력한다. 문제 풀이헷갈리는 조건 정리1. α 위치는 현재 진행하는 y방향의 그 다음 방향이다. α = ( cR + dir[cDir][0], cC + dir[cDir][1] )2. 토네이도가 이동할 때 현재 위치(x), 다음 위치(y) 값의 변화는 없다.3. α에는 각 위치에서의 비율만큼의 값을 뺀 값이다. 그냥 α 값에다가 현재 위치 값의 55%를 하면 안된다. 소숫점 ..