목록2024/04/21 (3)
체뚱로그
풀이 시간: 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%를 하면 안된다. 소숫점 ..