본문 바로가기

알고리즘/백준 문제풀기

BOJ 백준 17136 색종이 붙이기 #include #include #include using namespace std; const int SIZE = 10; int arrMap[SIZE][SIZE]; bool arrBoolMap[SIZE][SIZE]; int arrCount[5]; struct EmptySpace { int x, y; }; vectorvecEmptySpaces; intg_nCnt = 999999999; intg_nRemainArea = 0; boolg_bFind = false; void Input() { for (int i = 0; i < SIZE; ++i) { for (int j = 0; j < SIZE; ++j) { scanf("%d", &arrMap[i][j]); if (arrMap[i][j]) { g_nRemain..
BOJ 백준 1793 타일링 https://www.acmicpc.net/problem/1793 1793번: 타일링 문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. 출력 입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다. 예제 입력 1 복사 2 8 12 100 200 예제 출력 1 복사 3 171 www.acmicpc.net 11727 2xN 타일링 2번 https://onecoke.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-11727..
BOJ 백준 11727 2xN 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. www.acmicpc.net 2xN 타일링 https://onecoke.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-11726-2xN-%ED%83%80%EC%9D%BC%EB%A7%81 BOJ 백준 11726 2xN 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의.. onecoke.tistory.com 문제 ..
BOJ 백준 11726 2xN 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 풀이 ) 위의 사진을 볼 때 타일의 끝이 채워지는 방식은 위와 같이 두 가지 경우가 존재한다. 1. 길이가 1이 남고 1x2 타일로 채워진 경우 2. 길이가 2가 남고 2x1 타일 2개로 채워진 경우 타일의 끝에 길이가 3이 남는 경우는? n이 3인 타일이 채워지는 방식은 위와 같이 3가지 경우가 존재한다. 채워지는 방식 중, 첫 번째는길이가 1 남고 1x2 타일로 채워지는 경우 에 해당한다. 두 번째는 길이가 ..
BOJ 백준 2573 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 문제 풀이) 입력을 받을 때 총 빙산의 개수와 빙산의 위치를 저장해주고, vector에 빙산의 구조체를 넣어준다. 구조체에는 빙산의 좌표 x..
BOJ 백준 3055 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 문제 풀이 ) 1. 'D'와 'S', 즉 비버 굴과 고슴도치의 시작 지점은 하나씩만 주어진다고 되어 있지만, 물이나 돌은 그런 표현이 없다...
BOJ 백준 5014 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없 www.acmicpc.net 문제 풀이 ) 1. DP를 통한 풀이 ( 메모리, 시간 효율이 낮은 풀이 ) #include #define TOTAL 0 #define..
BOJ 백준 2931 가스관 < DFS> https://www.acmicpc.net/problem/2931 1. 방향 지정 UP : 0 , DOWN : 1, LEFT : 2, RIGHT : 3 로 가정 방향이 전환되는 블록은 '1', '2', '3', '4' 의 경우이다. '1' 블록의 경우 UP(0)의 방향을 RIGHT(3)로, LEFT(2)의 방향을 DOWN(1)로 전환 '2' 블록의 경우 DOWN(1)의 방향을 RIGHT(3)로, LEFT(2)의 방향을 UP(0)으로 전환 '3' 블록의 경우 DOWN(1)의 방향을 LEFT(2)로, RIGHT(3)의 방향을 UP로 전환 '4' 블록의 경우 UP(0)의 방향을 LEFT(2)로, RIGHT(3)의 방향을 DOWN(1)로 전환 따라서, '1' 블록의 경우 방향 = (본래 방향 + ..

티스토리툴바