2750번 수 정렬하기
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
정렬 알고리즘을 구현하자니 찾아보기 귀찮아서 (너무 솔직한가) sort()를 사용했다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(void) {
int n;
cin >> n;
vector<int> num(n);
for (int i = 0; i < n; i++) {
cin >> num[i];
}
sort(num.begin(), num.end());
for (int n : num) {
cout << n <<endl;
}
}2689번 달팽이는 올라가고 싶다
땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오
이 문제는 처음에 while문을 이용해 올라갔다 내려갔다를 반복해 day를 구하는 코드로 제출했는데 우아 시간 초과가 되었다. 음 이게 아니구나 싶어서 경우의 수를 나누어서 해보다가 계속 틀렸다. 세번 정도 틀렸고 생각보다 시간이 많이 흘렀다.
생각해보니 뭔가 낯익은 느낌이 중딩 시절 방정식 느낌이 스멀스멀나 day를 X로 생각하고 식을 간단하게 구했다. 어쨌든 3일이 걸리면 두 밤은 잤다는 이야기고 4일이 걸리면 세밤은 이미 잤다는 이야기이다.
위의 식과 같이 X의 최소값을 구할 수 있다. 예를 들어 우변이 2.22라면 X는 최소 정수값이어야 하므로 3이 된다. 그래서 ceil()함수를 이용해 올림을 해주었다. 새삼 이 문제를 보면서 무작정 코드를 치면 안된다는 것을 느꼈고 너무 간단해서 어이가 없었다.
#include<iostream>
#include<cmath>
using namespace std;
int main(void) {
int a, b, v;
cin >> a;
cin >> b;
cin >> v;
int day;
day = ceil( (double)(v - b) / (a - b));
cout << day;
}1924번 2007년
오늘은 2007년 1월 1일 월요일이다. 그렇다면 2007년 x월 y일은 무슨 요일일까? 이를 알아내는 프로그램을 작성하시오. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다.
1월1일 부터 입력받은 일까지 총합을 구해서 (월~금)7로 나머지 연산을 하면 요일이 튀어나올 것이다. 그래서 달마다 총 몇일인지 저장하는 배열과 출력을 위한 요일 배열을 두개 만들었다.
생각해보니 12월은 저장할 필요가 없는데 그냥 예의상 넣어줬다.
#include<iostream>
#include<vector>
using namespace std;
int main(void) {
vector<int> lastDay = { 31,28,31,30,31,30,31,31,30,31,30,31 };
vector<string>day = { "SUN","MON","TUE", "WED", "THU", "FRI", "SAT" };
int month;
int date;
cin >> month;
cin >> date;
int sumDate = 0;
for (int i = 0; i < month-1; i++) {
sumDate += lastDay[i];
}
sumDate += date;
cout << day[sumDate % 7];
}1193번 분수찾기
지그재그 방향별로 나오는 분수들을 나열해서 적어보니 필요한 변수들이 눈에 보였다. 먼저 방향이 바뀔때마다 방향에 포함되는 분수가 한 개씩 많아진다.
범위를 나타내는 range 변수
범위 안에서 입력된 X가 몇 번째 분수인지 알기 위한 idx 변수
범위의 시작과 끝을 저장하는 start, end변수 (=전체 나열에서 몇 번째인지)
그리고 대각선 위로 올라가는 방향이면 범위가 짝수
대각선 아래로 내려가는 방향이면 범위는 홀수이다.
두 경우로 구분해 x번째 분수를 출력한다.
#include<iostream>
using namespace std;
int main(void) {
int start = 1;
int end = 1;
int range = 1;
int input;
cin >> input;
while (1) {
if (start <= input && input <= end) {
int idx = input - start;
if (range % 2 == 0) {
cout << 1 + idx << "/" << range - idx;
}
else {
cout << range - idx << "/" << 1 + idx;
}
break;
}
range++;
start = end + 1;
end = start + range-1;
}
}2775번 부녀회장이 될테야
이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.
아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.해당 집의 거주민 수를 구해라
순환함수를 이용해야하나 했지만 반복문으로 푸는게 실행시간이 빠를 것 같아서 반복문으로 풀었다. 처음에 호와 층에 개수 제한이 있는지 몰라서 아예 아파트 구조를 만들어 놓기엔 어려움이 있다고 생각을 했다.
나중에 확인해보니 14층 14호로 제한이 있었다.
순환 함수보단 스택에 넣고 푸시팝을 하는게 덜 오래걸릴 것이라 생각했는데 이 또한 돌려보니 엄청나게 오래걸렸다. 그렇게 좋은 방법은 아닌 듯하다. 10층만 넘어서도 엄청 오래걸렸다.(사실 코드 자체도 순환함수로 구현한 사람이 더 간단해보였다.)
이문제에 가장 적절한건 아파트 구조를 미리 만들어 놓는 것으로 추측해본다. 문제 제한 사항을 주의깊게 읽어보는 것을 놓치지 말자.
#include<iostream>
#include<string>
#include<vector>
#include<utility>
using namespace std;
int main(void) {
//testcase 개수
int t;
cin >> t;
vector<pair<int, int>> testCase(t);
//testcase입력 받음
for (int i = 0; i < t; i++) {
cin >> testCase[i].first;
cin >> testCase[i].second;
}
for (int i = 0; i < t; i++) {
int k = testCase[i].first;
int n = testCase[i].second;
vector<pair<int, int>> position;
position.push_back(make_pair(k, n));
int people = 0;
while (position.size()) {
int tempK = position.back().first;
int tempN = position.back().second;
//cout << tempK << "층" << tempN << "호" << endl;;
position.pop_back();
if (tempN == 1) {
people++;
}
else if (tempK == 0) {
people += tempN;
}
else {
position.push_back(make_pair(tempK, tempN - 1));
position.push_back(make_pair(tempK - 1, tempN));
}
}
cout << people << endl;
}
}pair<int,int>
두 자료형의 쌍을 저장할 수 있는 구조이다. 처음에 vector<int,int> 이런걸 검색해보다가 발견하였다. 허허 무지하다. 이 문제처럼 층과 호수를 같이 입력받고 사용해야할 때 괜찮아 보인다.
#include<utility>
pair<int, int> p = make_pair(2, 3);
cout << p.first << endl; //2출력
cout << p.second << endl; //3출력