어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.
처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km 마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.
예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다.
제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2x5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3x2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1x4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2x5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4x2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.
각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.
[입력]
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.
[출력]
표준 출력으로 제일 왼쪽 도시에서 오른쪽 도시로 가는 최소 비용을 출력한다.
[서브태스크]
번호
배점
제한
1
17
모든 주유소의 리터당 가격은 1원이다.
2
41
2 ≤ N ≤ 1,000, 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터당 가격은 최대 10,000이다.
3
42
원래의 제약조건 이외에 아무 제약조건이 없다.
[알고리즘 분류]
그리디 알고리즘
[정답 코드]
#include <bits/stdc++.h>
using namespace std;
#define n 100001
long long N, v, price, s[n], r[n-1];
int main() {
cin >> N;
// 길 입력
for(int i=0;i<N-1;++i) cin >> r[i];
// 주유소 입력
for(int i=0;i<N;++i) cin >> s[i];
// v는 주유소 최소 가격
// 시작은 기름이 없는 상태로 다음 도시까지는 무조건 거리만큼 충전 = price(총 가격)
v = s[0]; price = v * r[0];
for(int i=1;i<N-1;i++) {
// 최소 주유 가격과 다음 도시의 주유 가격을 비교해 저장
v = min(v,s[i]);
// 최소 주유 가격과 다음 도시까지의 거리를 곱해 price에 추가
price += v * r[i];
}
cout << price;
}
화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.
자주 나오는 단어일수록 앞에 배치한다.
해당 단어의 길이가 길수록 앞에 배치한다.
알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다.
M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.
[입력]
첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100000, 1 ≤ M ≤ 10)
둘째 줄부터 N + 1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10을 넘지 않는다.
단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.
[출력]
화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.
[알고리즘 분류]
자료 구조
문자열
정렬
해시를 사용한 집합과 맵
트리를 사용한 집합과 맵
[해설]
주어진 단어장의 순서에 따라 정렬하는 법을 구상할 줄만 안다면 sort와 정렬 식을 이용해 쉽게 해결할 수 있는 문제였다.
[정답 코드]
#include <bits/stdc++.h>
using namespace std;
vector<string> wds;
unordered_map<string,int> nt;
int n, m;
string w;
bool cmp(string a, string b) {
// 단어의 길이가 같고 빈도수가 동일하다면 사전 순으로 정렬
if(a.size() == b.size() && nt[a] == nt[b]) {
return a < b;
}
// 빈도수가 동일하다면 길이 순으로 정렬
else if (nt[a] == nt[b]) {
return a.size() > b.size();
}
// 빈도수로 정렬
return nt[a] > nt[b];
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
while(n--) {
cin >> w;
// 주어진 단어의 길이가 m보다 크거나 같은 경우
if(w.length() >= m) {
// 만약 단어가 단어장에 이미 존재한다면 빈도수 + 1
if(nt[w]) nt[w]++;
// 존재하지 않는 경우 단어장에 빈도수 1로 저장한다.
else {
nt[w] = 1;
wds.push_back(w);
}
}
}
// 주어진 단어를 저장한 배열을 위의 cmp식에 따라 정렬한다.
sort(wds.begin(), wds.end(), cmp);
for(const auto& i : wds) cout << i << '\n';
}
: HTML 태그, ID, Class, 속성 등의 특성을 이용해 CSS 규칙을 적용할 요소를 선택하는 것을 말한다.
[기본선택자]
전체 선택자 : 모든 요소를 대상으로 하는 선택자로 *(애스터리스크) 문자를 이용해 지정한다.
* {
margin: 0; /* 모든 요소에 0 크기의 바깥 여백을 적용함. */
padding: 0; /* 모든 요소에 0 크기의 안쪽 여백을 적용함. */
}
Type 선택자 : 특정 요소를 대상으로 지정하는 선택자로 HTML 태그명을 이용해 대상을 선택한다.
/* p태그를 가진 모든 요소를 지정한다. */
p {
color: red;
text-decoration: underline;
}
/* h2태그를 가진 모든 요소를 지정한다. */
h2 {
font-size: 32px;
margin: 1rem;
}
Class 선택자 : 특정 요소를 대상으로 지정하는 선택자로 HTML 요소에 명시한 Class를 이용해 대상을 선택한다. ('.' + '클래스명' 형식으로 지정한다.)
/* 'mainTitle'라는 class명을 가진 모든 요소를 지정한다. */
.mainTitle {
font-size: 64px;
font-weight: bold;
margin: 18px;
}
ID 선택자 : 특정 요소를 대상으로 지정하는 선택자로 HTML 요소에 명시한 ID를 이용해 대상을 선택한다. ('#' + 'ID명' 형식으로 지정한다.)
/* 'username'라는 ID명을 가진 모든 요소를 지정한다. */
#username {
background: yellow;
font-weight: bold;
}
/* 'password'라는 ID명을 가진 모든 요소를 지정한다. */
#password {
text-decoration: wavy underline red;
}
속성 선택자 : 특정 요소를 대상으로 지정하는 선택자로 HTML 요소에 명시한 속성(attr)을 이용해 대상을 선택한다.
/* class 속성을 가진 모든 p태그 요소를 지정한다. */
p[class] {
color: green;
font-size: 12px;
}
/* class 속성에 "top" 값으로 시작하는 모든 p태그 요소를 지정한다. */
p[class^="top"] {
color: red;
}
/* class 속성에 "name" 값으로 끝나는 모든 p태그 요소를 지정한다. */
p[class$="name"] {
color: yellow;
}
/* href 속성에 "https://www.google.com" 값을 가진 모든 a태그 요소를 지정한다. */
a[href="https://www.google.com"] {
font-weight: bold;
}
/* href 속성에 "www" 값을 포함하는 모든 a태그 요소를 지정한다. */
a[href*="www"] {
background: royalblue;
}
/* class 속성에 "head" 값을 포함하는 모든 h1태그 요소를 지정한다. */
h1[class~=""] {
color: blue;
}
[그룹선택자]
선택자 목록 : 그룹 선택자(선택자 목록)은 쉼표(,)를 이용해 선택자들을 구분하여 나열해 다수의 요소를 지정한다.
/* p태그, class 속성을 가진 h1태그, ID명이 "head"인 요소를 모두 지정한다. */
p, h1[class], #head {
color: red;
}
[결합자]
자손 결합자 : 순서대로 오른쪽 요소가 왼쪽 요소의 자손으로, 공백을 기준으로 나열되어 가장 마지막에 명시된 자손 요소를 지정한다.
/* div안의 span이 가지고 있는 p요소를 지정한다. */
div span p {
color: yellow;
}
자식 결합자 : '>'를 기준으로 왼쪽 요소의 바로 하위(자식)인 요소를 지정한다.
/* div태그 하위에 존재하는 모든 p태그 요소를 지정한다.*/
div > p {
color: green;
}
일반 형제 결합자 : 같은 부모를 공유하면서 '~'를 기준으로 왼쪽 요소가 가장 첫 번째로 나타나는 위치 이후의 모든 오른쪽 요소를 지정한다. (가장 첫 번째 왼쪽 태그 이전에 나온 오른쪽 태그는 선택되지 않는다.)
/* h1태그 이후에 나오는 모든 li태그 요소들을 지정한다. */
h1 ~ li {
text-decoration: underline;
}
인접 형제 결합자 : 같은 부모를 공유하면서 '+'를 기준으로 왼쪽 요소 바로 뒤(이후)에 위치하는 오른쪽 요소를 지정한다.
/* h1태그 바로 뒤에 위치한 p태그 요소를 선택한다. */
h1 + p {
color: red;
}
long long p(long long A, long long Exp) {
if(Exp == 1) return A;
long long t = p(A, Exp / 2);
if(Exp % 2 == 1) return t * t * A;
return t * t;
}
그 다음으로 생각해보아야 하는 것이 모듈러 연산이다.
위에 주어진 식에 그냥 c로 나누게 되면, 즉 다음과 같은 식( t * t * A % c )을 만들게 되면 틀린 값이 나오게 되는데, 이는 문제에서 입력으로 주어지는 A, B, C 중 A와 B가 최댓값 2,147,483,647으로 주어지게 되는 경우 t * t 식에서 long long의 범위를 넘어가 잘못된 계산이 진행되기 때문이다.
( t * t * A % c ) 식에 모듈러 연산( (a * b) % c = (a % c * b % c) % c )을 적용해 올바르게 식을 구성해보면 다음과 같이 나타낼 수 있다.
(t * t * A) % c = ((t * t % c) * (A % c)) % c
= (((t * t % c) % c) * (A % c)) % c
= ((t * t % c) * A) % c
이렇게 구성한 식을 이용해 리턴값을 다음과 같이 재구성해주면 된다.
long long p(long long A, long long Exp) {
if(Exp == 1) return A % c;
long long t = p(A, Exp / 2);
if(Exp % 2 == 1) return (t * t % c) * A % c;
return t * t % c;
}
[정답 코드]
#include <ios>
long long a, b, c, k;
long long p(long long A, long long Exp) {
if(Exp == 1) return A % c;
long long t = p(A, Exp / 2);
if(Exp % 2 == 1) return (t * t % c) * A % c;
return t * t % c;
}
int main() {
scanf("%lld%lld%lld",&a,&b,&c);
printf("%lld",p(a, b));
}
N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.
먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.
예시'
별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.
[입력]
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
[출력]
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.
[알고리즘 분류]
다이나믹 프로그래밍
슬라이딩 윈도우
[해설]
해당 문제는 "위에서부터 내려오면서 값을 더해온"라는 개념이 아닌, "아래의 값은 위에서 어떤 값을 가져와야 크거나 작은 값을 가질 수 있는가?"를 생각하면서 해결하면 쉽게 해결할 수 있었다.
그림으로 나타내면 다음과 같이 나타낼 수 있다.
[정답 코드]
#include <bits/stdc++.h>
using namespace std;
// a배열은 현재 칸으로 입력되는 숫자배열
// 최솟값, 최댓값을 누적해가며 도출할 배열 mn과 mx, 그리고 이전 값을 임시로 저장할 t0~2를 선언한다
int n,a[3],mn[3],mx[3],t0,t1,t2;
int main(){
cin >> n;
while(n--){
// 현재 칸 입력받기
cin >> a[0] >> a[1] >> a[2];
// 최솟값 누적
t0 = mn[0]; // 이전 줄의 첫 번째 누적값
t1 = mn[1]; // 이전 줄의 두 번째 누적값
t2 = mn[2]; // 이전 줄의 세 번째 누적값
// 이전 줄의 각 누적값들을 비교해 더 작은 값을 현재 칸의 값과 더해 저장한다
mn[0] = min(t0,t1) + a[0];
mn[1] = min({t0,t1,t2}) + a[1];
mn[2] = min(t1,t2) + a[2];
// 최댓값 누적
t0 = mx[0];
t1 = mx[1];
t2 = mx[2];
// 이전 줄의 각 누적값들을 비교해 더 큰 값을 현재 칸의 값과 더해 저장한다
mx[0] = max(t0,t1) + a[0];
mx[1] = max({t0,t1,t2}) + a[1];
mx[2] = max(t1,t2) + a[2];
}
// 누적된 각 값들의 배열에서 최댓값, 최솟값을 순서대로 출력한다
cout << max({mx[0],mx[1],mx[2]}) << " " << min({mn[0],mn[1],mn[2]});
}
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
[입력]
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
[출력]
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
[알고리즘 분류]
다이나믹 프로그래밍
[해설]
문제의 설명을 보면 이 문제는 주어진 값을 가지고 특정 위치에서 시작하여 끝까지 값을 중복해 나가 정답을 구하는 문제임을 알 수 있다. 문제에서는 위에서부터 내려오면서 수의 합이 최대가 되는 경로를 구한다고 하고있지만 코드를 이와 같이 작성할 경우 n의 크기가 커질 수록 아래층에서의 분기점이 많아지게 되어 계산 과정이 복잡하게 될 것이다.
하지만, 정수 삼각형의 아래에서 두 숫자끼리 비교해가며 더 큰 수를 윗 층의 숫자에 중복해 나가는 방식으로 풀게되면 복잡한 비교 과정이 단순하게 변하게 된다.
문제에서 주어진 예시로 표현해보자면 다음과 같이 나타낼 수 있는 것이다.
아래에서부터 좌우의 숫자들을 비교해 큰 값을 위로 더하여 나간다.
[정답 코드]
#include<bits/stdc++.h>
using namespace std;
int n, M[501][501];
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<i+1;j++)
scanf("%d",&M[i][j]);
for(int i=n-1;i>=1;i--)
for(int j=0;j<i;j++)
M[i-1][j] += max(M[i][j],M[i][j+1]);
printf("%d",M[0][0]);
}
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
[입력]
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
[출력]
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
[알고리즘 분류]
다이나믹 프로그래밍
[해설]
이번 문제는 집들의 색깔이 이전 색과 겹치지 않도록 칠하며, 그 중에서도 비용이 최소가 되는 결과를 구하는 문제이다.
해당 문제를 작게 나누어 생각해보면,
"'집i'가 빨간색이 되기 위해서는 '집i-1'가 초록색 혹은 파란색이어야 한다."
"'집i'가 파란색이 되기 위해서는 '집i-1'가 빨간색 혹은 초록색이어야 한다."
"'집i'가 초록색이 되기 위해서는 '집i-1'가 빨간색 혹은 파란색이어야 한다."
로 나타낼 수 있다.
즉, r에는 (g와 b 중 더 작은 값 + 현재 집을 빨강으로 칠하는 비용)을 중복해 나가고, g에는 (r과 b중 더 작은 값 + 현재 집을 초록으로 칠하는 비용)을, b에는 (r과 g중 더 작은 값 + 현재 집을 파랑으로 칠하는 비용)을 지속적으로 중복하고 이들 중 최솟값을 선택하게 되면 그 값이 모든 집을 칠하는 비용의 최솟값이 된다.
[정답 코드]
#include<bits/stdc++.h>
using namespace std;
int main() {
int N,r=0,g=0,b=0,i,j,k,nr,ng,nb;
cin >> N;
while(N--) {
cin >> i >> j >> k;
nr=min(g,b)+i;ng=min(r,b)+j;nb=min(r,g)+k;
r=nr; g=ng; b=nb;
}
cout << min({r,g,b});
}
