프로그래밍/백준 알고리즘
백준 알고리즘 풀이 6359번 - 만취한 상범
good programmer
2019. 10. 7. 14:43
https://www.acmicpc.net/problem/6359
6359번: 만취한 상범
문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고
www.acmicpc.net
- dp 문제.
- 알고리즘 -
입력받은 방의 수에서 가장 큰 걸 골라서 그 방수까지 dp를 수행.
dp 수행 식
|
1
2
3
|
if ((int)sqrt( i+1) * (int)sqrt(i+1) == (i+1)) ans[i+1]=ans[i]+1.
else ans[i+1]=ans[i]
|
cs |
-시간 복잡도-
가장 큰 방 수를 고르는 시간복잡도 = O(N).
dp식 시간복잡도 = O(N)
따라서 총 시간 복잡도 = O(N)
- 예외 조건 -
1. sqrt() 함수는 반환값이 double형이다. 따라서 int형으로 type casting 할 경우 소숫점 뒷자리들을 다 날려버린다.
쉽게 풀 수 있는 문제였다.
-소스 코드-
|
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
|
#include <iostream>
#include <cmath>
using namespace std;
int arr[101];
int main()
{
int testCase;
int num=0;
cin>>testCase;
for(int i=1;i<=testCase;i++){
cin>>arr[i];
if(num<arr[i]) num=arr[i];
}
int counts[101];
counts[1]=1;
for(int i=1;i<=num;i++){
if((int)sqrt(i+1)*(int)sqrt(i+1)==(i+1)){
counts[i+1]=counts[i]+1;
}
else{
counts[i+1]=counts[i];
}
}
for(int i=1;i<=testCase;i++){
cout<<counts[arr[i]]<<endl;
}
}
|
cs |
틀린 내용이나 지적 언제나 환영입니다.
도움이 되었다면 하트 한번씩 눌러주세요:)