목록알고리즘/백준 (65)
개발자 김수진
[문제] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net [풀이] 아기 상어와 물고기가 존재. 아기 상어는 자신보다 작은 물고기들을 잡아먹을 수 있다. 아기 상어는 자신보다 큰 물고기가 존재하는 칸은 지나가지 못한다. 아기 상어는 1칸 움직이는데 1초 걸린다. 아기 상어가 자신의 크기만큼 물고기를 먹는다면 크기가 1 증가한다. ( 크기가 3인 상어가 물고기 3마리를 먹으면 크기가 4가 된다.) 입력으로는 공간의 크기와 상태가 주어진다..
[문제] https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net [풀이] N,M,K가 주어지고 K년 후에 남아있는 나무의 수를 출력하면 된다. 따라서 for 문을 K년 동안 돌리고 for문에서 봄, 여름, 가을, 겨울에 대한 함수를 호출했다. 봄 - 에는 나무가 영양분을 먹는다. 단, 한 좌표에 나무가 2개 이상이면 나이가 어린 순서부터 영양분을 먹는다. 영양분이 부족하다면 먹지 못하고 나무는 죽는다. 여름 - 봄에 죽은 나무가 양분으..
[문제] https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net [풀이] 인구 차가 L 이상, R 이하라면 queue와 vector에 넣어서 인구 이동 할 수 있는 좌표 모두 구하고 마지막에 인구 평균 구하고 map을 평균 값으로 update 해준다. queue는 BFS로 풀기 위해서 사용 vector는 나중에 인구 이동 하고 인구 수 update 하기 위한 좌표들 저장 solve 함수에서 평균 인구 수 구하고 vector에 저장된 ..
[문제] https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감�� www.acmicpc.net [풀이] DFS를 사용해 각 CCTV에 대해 모든 경우의 수를 따져주고 최솟값을 구하면 된다. [그림 1]과 같이 DFS 함수에서 visited 배열에 CCTV가 감시할 방향을 저장해놓고 모든 CCTV에 대해 저장했다면 solve 함수에서 방향에 맞게 감시 진행 이런 방식으로 spread 함수에서 좌표랑 방향을 인자 값으로 넘겨주고 벽을 만나기 전까지 감시할 수 있는 좌표에..
[문제] https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 시뮬레이션 문제로 높이가 같은 경우 -> 다음 index로 넘어감 높이가 다른 경우 -> 차이가 1보다 큰지 확인 행과 열을 올렸다 하나의 일차원 배열에 옮겨서 확인 (어차피 행과 열 확인하는 방법은 같으니까) [풀이] 1. check 함수 다음 인덱스랑 높이 비교 높이차가 같은 경우 다음 인덱스로 넘어감. 높이차가 1보다 크다면 check 함수 바로 return. 높이차가 1인 경우 comp 함수 호출. 0부..
벡터 시간 오래 걸릴까봐 안 쓰고 풀었는데 오히려 벡터 사용하니까 더 빠르다. DFS로 접근 - 벡터 대신 반복문 사용 시간 : 124ms #include #define MAX 20 using namespace std; int N; int map [MAX][MAX]={0,}; int visited[20]={0,}; int MIN = 1e9; void solve() { int start=0; int link=0; for(int i=0;i N; for(int i=0;i
[풀이 1] 처음에 시뮬레이션인줄 알고 조건 하나씩 다 따지면서 아래와 같이 구현 #include using namespace std; //0: 빈칸, 1:벽 int N,M; int map[50][50]; int dir; int x,y; int cnt=0; // number of clean space by robot //0:북 , 1:동, 2:남, 3:서 int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1}; int main(void) { cin >> N >> M ; cin >> x >> y >> dir; for(int i=0;i map[i][j]; } while(1){ if(map[x][y]==0){ map[x][y]=2; //현재 위치 청소 cnt++; } int pdi..
#include using namespace std; int N,M,K; int map[20][20]={0,}; int x,y; int dx[4] ={0,0,-1,1}; int dy[4] = {1,-1,0,0}; int dice[7]={0,}; //지도 위 : 1 , 동쪽 : 3 , // 처음 주사위 모든 면에 0 // 이동한 칸이 0인 경우 -> 주사위에 있는 숫자가 바닥면으로 // 0이 아닌 경우 -> 주사위로 복사되고 칸은 0으로 int main(void) { cin >> N >> M >> x >> y >> K; for(int i=0;i map[i][j]; } for(int i=0;i> dir; int nx = x + dx[dir-1]; int ny = y + dy[dir-1]; if( nx < 0..