목록문제풀이 (18)

마이 플밍 블로그

[C++] 백준 5567 - 결혼식

5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 1번 노드부터 시작해서 연결된 간선들을 탐색하며 한번 방문했으면 답에 추가하고 이미 방문했다면 연결된 간선들을 탐색만 한다. 탐색을 할때마다 카운트를 1증가시키며 카운트가 2가되면 answer을 반환한다. 코드 #include using namespace std; int n, m; int flag[501]; vector friends[501]; int Find(int u, int c){ int answer = 0; if(flag[u] == 0..
문제풀이/백준 2023. 2. 26. 22:43
[C++] 백준 1937 - 욕심쟁이 판다

1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 평범하게 모든타일에서 시작해서 탐색하면 시간초과에 걸린다. 메모이제이션을 이용하면 쉽게 통과할 수 있다. 코드 #include using namespace std; int board[501][501]; int dp[501][501]; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; int answer = 0; int n; bool InMap(int x, int y){ if( 0 n; priority_queue..
문제풀이/백준 2023. 2. 26. 22:05
[C++]백준 11780 - 플로이드2

11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 플로이드-워셜 알고리즘에서 경로추적을 추가하면 되는 문제다. 문제는 쉬웠으나 못가는 경우 0을 출력하는걸 깜빡해서 여러번 틀렸다. 코드 #include #include using namespace std; #define CITY 105 #define INF 200000000 int map[CITY][CITY]; int nextNode[CITY][CITY]; int n, m; void FloydWarshall(){ for(int i = 1; i n >> m..
문제풀이/백준 2022. 12. 13. 23:50
[C++]백준 1051 - 숫자 정사각형

https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 풀이 가장 큰 정사각형의 크기를 구하면 되기 때문에 순회중인 타일의 위치를 (x, y)라고 하고 정사각형의 변의 길이를 i라고 하면 (x+i, y) (x, y+i) (x+i, y+i) 위치의 타일이 순회중인 타일의 번호가 같으면 넓이 비교를 하면 된다. 코드 #include #include using namespace std; int map[100][100]; int flag[100][100][4..
문제풀이/백준 2022. 3. 15. 17:33
[C++]백준 1708 - 볼록 껍질

https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 문제에선 Convex Hull에 대한 설명을 하는데 Convex Hull이란 가장 바깥쪽에 있는 정점들을 이어서 만드는 볼록 다각형을 뜻한다. 이런 Convex Hull을 만드는 알고리즘 중에서는 Graham's Scan 알고리즘이 있다. 이 문제는 Graham's Scan 알고리즘으로 풀었는데 이 알고리즘에 대해 설명하자면먼제 Convex Hull을 자세히보면 이어진 정점들이..
문제풀이/백준 2022. 3. 15. 03:44
[C++]백준 14226 - 이모티콘

https://www.acmicpc.net/status?user_id=dkak14&problem_id=14226&from_mine=1 채점 현황 www.acmicpc.net 코드 #include #include #include using namespace std; int S; int IMT[1003][1003]; int answer = 98765432; void CalIMT(int imtnum, int clipboard, int count) { if (answer S) return; if (IMT[imtnum][clipboard] S; memset(IMT, 5, sizeof(IMT)); CalIMT(1, 0, 0); cout
문제풀이/백준 2022. 1. 11. 02:15
[C++]백준 12869 - 뮤탈리스크

https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 풀이 DP로 푸는 문제다. 모든 경우의 수를 탐색해서 제일 빨리 SCV를 다 처치하는 경우를 찾는다 코드 #include #include #include #include #include #include using namespace std; #define MAX 987432 int N; int SCVHP[4]; int SCV[61][61][61]; int n = 0; void Mutalisk(int scv1..
문제풀이/백준 2022. 1. 10. 23:01
[C++]백준 2481 - 데스노트

2281번: 데스노트 첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m www.acmicpc.net 풀이 DP를 이용해 푸는 문제다. 한줄 넘기고 이름을 쓰는 경우와 넘기지 않고 이어서 이름을 쓰는 경우 두가지로 나누어서 풀면된다. 코드 #include #include #include using namespace std; int m,n; int name[1001]; int dp[1001][1001] = {0}; int DeathNote(int nameIndex, int length) { if (nameIndex >= n) { r..
문제풀이/백준 2022. 1. 10. 19:32
이전 Prev 1 2 3 Next 다음