백준72 [백준][C++] 2302번: 극장 좌석 <239> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 HTML 삽입 미리보기할 수 없는 소스 1) 일반석 1자리만 있는 경우 당연히 해당 1자리만 앉으면 끝이니 1가지 경우이다. DP[1] = 1 이 된다. 2) 일반석 2자리만 있는 경우 이 경우는 2가지 경우가 가능한데, 다음과 같이 가능하다. [A][B] [B][A].. Algorithm/백준 2022. 8. 16. [백준][C++] 15486번: 퇴사 2 <238> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 N의 범위가 150만 이라서 완전탐색 이런 방식으로는 절대 해결할수 없다 생각하였다. 그리고 문제 자체에서 DP smell이 엄청나게 느껴졌다. 바로 동적계획법을 적용시켜보려 노력하였다... Algorithm/백준 2022. 8. 9. [백준][C++] 17143번: 낚시왕 <237> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 아... 캐어렵다... 구현할 부분이 생각보다 많고, 생각해야 될점도 많다... 먼저 문제의 진행방식을 크게 3단계로 나눌 수 있다. 1. 배열 초기화 하기 2. 사람이 상어 낚시하기 3. 모든 상어 움직이고, 잡아먹기 ▶ 배열 초기화 하기 이때 맨 처음 초기화 가.. Algorithm/백준 2022. 7. 28. [백준][C++] 10775번: 공항 <236> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 원래 나의 첫 풀이는 Greedy 방식으로 매우 직관적인 코드를 작성했었다. 그냥 맨 뒤부터 확인하면 되겠다 생각 하였다. 따라서 맨 처음 나의 코드는 다음과 같았다. (73%에서 시간 초과 나는 코드) #include #include using namespace std; #define MAX 100001 int G, P; int cnt; vector air; bool gate[MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> G >> P; for (in.. Algorithm/백준 2022. 7. 26. [백준][C++] 1541번: 잃어버린 괄호 <235> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 일단 생각보다 잘 안풀렸던 문제... 문자열 파싱이야 쉬운데... 최소의 값을 어떤 방식으로 만들것인가? 이걸 생각 못해서... 다른 블로그의 글을 참고하였다. 생각보다 간단하다, - (음수) 부호 뒤의 모든 수.. Algorithm/백준 2022. 7. 18. [백준][C++] 1074번: Z <234> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 일단 재귀문제인건 당연하게 느껴진다. 재귀 문제는 항상 "나 안에 나 찾기" 를 한다는 생각으로 접근하다보면 실마리가 보인다. 재귀 함수에 들어왔을때, 우리가 원하는 칸에 도착했다면 출력하고 바로 종료시킨다... Algorithm/백준 2022. 7. 11. [백준][C++] 4386번: 별자리 만들기 <233> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 최소 신장 트리(MST)가 가장 먼저 떠오르는 문제이다. 다만 다른 MST 문제와 다른 점은 간선(edge) 정보가 주어지지 않는다는 점 이다. 따라서 사용자가 직접 모든 간선을 만들어 주어야 한다. 따라서나는 2중 f.. Algorithm/백준 2022. 7. 10. [백준][C++] 12893번: 적의 적 <232> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/12893 12893번: 적의 적 첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 적의 적을 구한다는 점 에서, 분리집합 즉, Union Find가 가장 먼저 떠올랐다. (ps 다른 방식으로는 1, -1, 1, -1 이런식으로 표식을 남기는 방법을 떠.. Algorithm/백준 2022. 7. 7. [백준][C++] 20040번: 사이클 게임 <230> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 대표적인 Union Find 문제인것 같다. Union Find 알고리즘이 궁금하다면 다음 글을 읽어보길 권장한다. https://blogshine.tistory.com/103 Algorithm/백준 2022. 6. 23. [백준][C++] 16724번: 피리 부는 사나이 <229> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 이 문제를 보고 생각한 방식은 cycle을 찾는 방식이였다. 우리 문제의 예시 를 생각해보자! 3 4 DLLL DRLU RRRU 우선 맨 왼쪽 위 부터 탐색을 시작한다고 해보자.. Algorithm/백준 2022. 6. 22. [백준][C++] 9328번: 열쇠 <228> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 이 문제를 가장 쉽게 해결하기 위해서는 지도의 태두리를 이동할수 있는 길('.') 로 만들어야 한다. 다음 그림을 살펴보자. 위 그림과 같이 초록색 부분이 원래의 MAP이고, 회색 영역이 우리가 추가해준 부분이다. 이는 외부.. Algorithm/백준 2022. 6. 10. [백준][C++] 1389번: 케빈 베이컨의 6단계 법칙 <227> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 일단 모든 구성원들 자신의 케빈수를 다 구해야 한다는 점에서 플로이드-와샬 방식을 선택하였다. 크게 어려운 부분은 없는데, 생각 못한 부분이 있어 이를 적어본다. if (MAP[i][k] != 0 && MAP[k][j] != 0) { .. Algorithm/백준 2022. 6. 8. 이전 1 2 3 4 5 6 다음
