본문 바로가기

Computer Science/Algorithm

 (24)
[BOJ 14890] 경사로 N X N 크기의 맵에 가로 N개 세로 N 개를 더해서 총 2N 개의 길이 있다. 각 지점에는 숫자가 써 있는데 높이를 나타낸다. 숫자가 같은 곳만 이동할 수 있는데 여기에서 경사로가 주어진다. 길이 L , 높이는 1로 고정되어있다. 경사로의 갯수는 무한하며 이 경사로들을 적절히 활용해 지나갈 수 있는 길의 갯수를 출력한다. 제약조건은 문제에 명시되어 있다. 문제 풀이 : 한 행, 한 열 씩 뜯어서 제약 조건에 위배가 되면 false 를 return 하는 check 함수 만들어 정답을 찾아냈다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636..
[BOJ 14889] 스타트와 링크 N(짝수인 정수)가 주어졌을때 2팀으로 나누어 팀간의 능력치를 최소화하는 문제이다. 문제 풀이 : 팀을 나눌 수 있는 모든 경우를 다 본다음 능력치 차이의 최솟값을 출력했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #include using namespace std;int N;int ans;void solve(vector &map, vector v) { int arr[2] = {0,0}; for (int i = 0; i > N; vector map(N+1, vector(N+1)); for (int i = 1; i map[i][j]; } } vec..
[BOJ 14891] 톱니바퀴 각 톱니바퀴가 맞닿은 부분의 극이 반대라면 회전하고 같으면 회전하지 않는다. 이 때 입력으로 들어오는 모든 회전을 한 뒤 최종 톱니바퀴의 상태에 따라서 점수가 부여되는데 그 점수의 합을 구하는 문제이다. 문제 풀이 : 단순한 구현문제로 입력으로 들어온 회전을 할 때 마다 1,2,3,4 톱니바퀴의 회전방향을 저장한뒤 마지막에 다 돌려주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 ..
[BOJ 14888] 연산자 끼워넣기 N개의 수들이 들어오면 N-1 개의 주어진 +,-,*,/ 연산자로 적절히 배열해 최댓값과 최솟값을 구하는 문제다. 수들의 배열은 바뀌지 않는다.시간 복잡도는 N-1개의 연산자들을 나열하는 것이므로 (N-1)! 이 되겠다. N의 최댓값이 11이므로 N-1은 10 즉 ,10! = 3628800 이다. 완전탐색을 이용해 풀었다. 주의할 점은 최솟값이 음수가 나올 수 있다는 점이다. 이 점 때문에 몇번이나 틀렸다... 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include using namespace std;int N;int a, b;void solve(vector &num, int p..
[BOJ 14501] 퇴사 이 문제는 상담할 수 있는 N일이 주어지고 상담을 마치는데 걸리는 시간과 상담을 했을 때 얻는 수익이 주어진다. N+1일날 퇴사를 하고자 할때 남은 N일 동안 상담을 진행하여 낼 수 있는 최대 수익을 구하는 문제다. 문제 풀이 : 각 날에 상담을 한다 / 안 한다로 구분하여 모든 경우의 수를 탐색해 최대 수익을 계산했다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include using namespace std; int N;int ans; void solve(vector &v, int day, int pay) { if (day > N) { return; } if (day==N) { if (ans > N; ..
삼성 SWEA 점심 식사시간 이 문제는 주어진 맵에 사람은 1로 계단은 2이상의 정수로 표현되어 나타난다. 계단은 무조건 2개이며 사람들은 1번 계단 혹은 2번 계단으로 모두 점심 식사를 하러간다. 이 때 계단으로 표현된 2 이상의 정수는 계단을 내려가는 소요시간을 뜻한다. 계단으로 이동하는 소요시간은 계단의 위치를 x,y 사람의 위치를 a,b 라 했을 때 |x-a|+|y-b| 로 표현된다. 동시간에 사람들이 한 계단에 도착할 수 있는데 최대 3명까지밖에 계단을 한 번에 내려갈 수 없다. 즉, 3명이 계단을 내려가고 있는 중이라면 4번 째 오는 사람은 계단에서 대기해야한다. 계단 입구에 도착하면 1분 후 내려갈 수 있다고 나오는데 애초에 사람과 계단사이의 거리를 구할 때 +1을 해 놓은 상태로 하면 훨씬 편하다. 사람들이 1 또는 ..
[BOJ 16137] 견우와 직녀 https://www.acmicpc.net/problem/16137 (견우와 직녀) 이 문제는 N X N 크기의 지도에서 견우가 (0,0)에서 출발해 (N-1, N-1)까지 가는 최단경로를 구하는 문제이다. 다만 몇 가지 제약사항이 있다. 바로 까치와 까마귀가 오작교를 만들어줘야하는데 노령화(?)로 인해 직녀에게 가는 오작교를 한 번에 만들지 못한다. 그리고 만든다고 해도 지나갈 수 있는 시간이 정해져 있다. 맵은 모두 3가지의 숫자를 가진다. 0: 절벽1: 견우가 지나갈 수 있는 곳2 이상의 정수 : 이미 설치된 오작교, 정수는 오작교의 주기를 의미한다. 만약, 주기가 3인 오작교를 까치와 까마귀가 만든다면 0분, 3분, 6분, 9분 ... 에는 지나갈 수 있고 나머지 시간인 1분 , 2분, 4분, 5..
[BOJ 9095] 1, 2, 3 더하기 접근 방법 : 주어진 수를 1,2,3 으로 만들 수 있는 방법을 모두 만들어 보면 된다. 재귀를 돌리면서 가능한 경우의 수를 모두 만든다. 1234567891011121314151617181920#include using namespace std;int ans = 0;void solve(int n) { if (n == 0) { ans += 1; return; } if (n >= 1) { solve(n - 1); } if (n >= 2) { solve(n - 2); } if (n >= 3) { solve(n - 3); }}int main() { int T; cin >> T; for (int i = 1; i > n; solve(n); cout

티스토리툴바