본문 바로가기

Computer Science/Algorithm

 (24)
[BOJ 1748] 수 이어 쓰기1 접근 방법 : 결과적으로 푼 방법은 1부터 1억까지 돌면서 각 숫자마다 자리수가 몇인지 일일히 세서 더한다. 123456789101112131415161718192021#include using namespace std; int len(int n) { int cnt = 0; while (n) { n = n / 10; cnt++; } return cnt;}int main() { int N; int ans = 0; cin >> N; for (int i = 1; i
[BOJ 6064] 카잉 달력 접근 방법 : 저번에 풀었던 '날짜 계산' 문제와 유사하다. 똑같은 방법으로 풀려고 했지만 시간초과가 나서 당황했다. M과 N값의 범위가 40000이므로 처음부터 M*N 까지 탐색을 시도했다간 엄청난 연산 숫자에 시간초과가 난다. 따라서 더 효율적인 방법을 찾아야 했는데 내가 생각해낸 방법은 아래와 같다. L번째 년도라고 했을 때 L = M*(몫) + x (주어진 x 값) 을 만족한다. 따라서 몫을 반복문을 증가시키면서 일단 x가 의미하는 L 번째 연도를 찾고 그 L번째 년도가 (L-y) / N 을 만족한다면 찾은 L 값이 정답이 된다. L의 범위는 최대 M*N을 넘지 않으므로 반복문을 M*N까지 돌려준다. 만약 L 값이 M*N 값을 넘게 되면 -1을 리턴한다. 12345678910111213141516..
[BOJ 14500] 테트로미노 접근 방식 : 어떻게 접근해야 할지 몰라서 http://suriisurii.tistory.com/26 surisuri 님 풀이 방법을 참고해 풀었다. ㅗ ㅓ ㅏ ㅜ 도형을 제외한 모든 도형이 dfs로 접근 가능하다는 사실을 깨닫지 못해서 힘들었던 것 같다. ㅗ ㅓ ㅏ ㅜ 도형을 따로 만들어 둔 뒤에 완전 탐색을 돌리면서 최댓값을 뽑아냈다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include using namespace std;int N, M;int dx[4] = { -1,1,0,0 };int dy[4] ..
[BOJ 1107] 리모컨 접근 방식 : 채널 0 번부터 차례대로 가면서 목표 채널과 차이의 최솟값을 출력했다. 반복문을 돌면서 해당 채널로 갈 수 있는 버튼이 고장나지 않았다면 목표채널과 해당채널의 차이의 최솟값을 갱신했다. 디폴트 채널이 100이므로 100에서 +,- 로만 목표채널로 갈 수 있는 값을 저장하여 번호 입력으로 이동할 수 있는 최솟값과 비교했다. 0번 채널의 예외처리를 안했다가 엄청 틀렸다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #define Min(a,b) a N >> M; for (int i = 0; i > c; remote[c] ..
[BOJ 1476] 날짜 계산 접근 방식 : E, S ,M 값의 주기는 1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19 이다. 준규가 사는 나라의 년도를 X로 했을 때, 입력으로 주어지는 E,S,M은 X를 각 변수의 최대값으로 나눈 나머지라고 볼 수 있다. 즉, E를 예로 든다면 X = aM + E (M은 몫) 관계가 성립한다. 따라서 X의 값은 X-E, X-S, X-M 을 각각 15, 28, 19 로 나누었을 때 동시에 나머지가 0이 되는 숫자중 최솟값이다. 1년도부터 시작해서 하나하나 체크하면서 X 값이 될 수 있는지 판단했다. 문제는 범위를 어디까지 돌려야하냐는건데 세 수의 주기를 보면 15,28,19 인데 이 세 수는 모두 서로소이다. 세 수가 모두 서로소 라는건 주기가 15*28*19라는 얘기다. 예를 들어 E..
삼성 S/W expert 2115번 벌꿀 채취 2115번 벌꿀 채취- N*N 크기의 map에 벌꿀의 양이 각각 들어가 있다. 2명의 사람이 벌꿀을 채취하는데 벌꿀을 가로 형태로만 채취할 수 있고 주어진 통의 갯수만큼만 채취 가능하다. 예를 들어 M=2 이면 {(0,0), (0,1)} 칸의 벌꿀을 채취할 수 있다. 채취한 벌꿀을 제곱하고 더해 Profit을 계산할 수 있다. 8, 9를 채취했다면 64+81 = 145 가 Profit이 된다. 여기서 최대로 채취할 수 있는 벌꿀의 양이 주어진다. 2명의 사람이 영역을 겹치지 않고 벌꿀을 채취했을 때 가장 큰 Profit을 구하는 문제다. - 우선 2명의 사람이 겹치지 않게 영역을 나눴고, 최대 이익을 산출하기 위해 비트 마스킹으로 나올 수 있는 모든 이익을 계산했다. 12345678910111213141..
삼성 S/W expert 2117번 홈 방범 서비스 2117번 홈 방범 서비스 - K가 1부터 증가하며 마름모 형태로 방범 서비스를 할 수 있는 구역이 점차 넓어진다. 서비스 범위가 넓어질 수록 드는 비용이 증가한다. 각 가구가 지불 할 수 있는 금액을 M 이라고 했을 때, (가구수 * 지불할 수 있는 비용) - (서비스 비용) 이 손해가 나지 않는, 즉 음수가 되지 않는 선에서 서비스할 수 있는 최대 가구수를 묻는 문제이다. 각 위치마다 전체 맵을 모두 탐색할 수 있을 만큼 K의 크기가 증가하며 bfs를 돌았다. 가구수를 따로 체크해주면서 최대 가구수를 계속 갱신하는 식으로 구현했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152..
삼성 S/W expert 2382번 미생물 격리 2382번 미생물 격리 문제 - 2차원 배열인 map을 2개 선언해서 움직일 때마다 미생물의 움직임을 배열에 번갈아가면서 저장하고 나중에 모든 미생물의 갯수를 출력했다. 코드가 너무 더러워서 이렇게 풀고 싶지 않다. 다른 방법을 찾아봐야겠다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231..

티스토리툴바